ObjFW
OFHuffmanTree.h
1 /*
2  * Copyright (c) 2008-2024 Jonathan Schleifer <js@nil.im>
3  *
4  * All rights reserved.
5  *
6  * This program is free software: you can redistribute it and/or modify it
7  * under the terms of the GNU Lesser General Public License version 3.0 only,
8  * as published by the Free Software Foundation.
9  *
10  * This program is distributed in the hope that it will be useful, but WITHOUT
11  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
12  * FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License
13  * version 3.0 for more details.
14  *
15  * You should have received a copy of the GNU Lesser General Public License
16  * version 3.0 along with this program. If not, see
17  * <https://www.gnu.org/licenses/>.
18  */
19 
20 #include <stdbool.h>
21 #include <stdint.h>
22 
23 #import "macros.h"
24 
25 #import "OFInvalidFormatException.h"
26 
27 OF_ASSUME_NONNULL_BEGIN
28 
29 typedef struct _OFHuffmanTree {
30  struct _OFHuffmanTree *_Nullable leaves[2];
31  uint16_t value;
32 } *OFHuffmanTree;
33 
34 /* Inlined for performance. */
35 static OF_INLINE bool
36 _OFHuffmanTreeWalk(id _Nullable stream,
37  bool (*bitReader)(id _Nullable, uint16_t *_Nonnull, uint8_t),
38  OFHuffmanTree _Nonnull *_Nonnull tree, uint16_t *_Nonnull value)
39 {
40  OFHuffmanTree iter = *tree;
41  uint16_t bits;
42 
43  while (iter->value == 0xFFFF) {
44  if OF_UNLIKELY (!bitReader(stream, &bits, 1)) {
45  *tree = iter;
46  return false;
47  }
48 
49  if OF_UNLIKELY (iter->leaves[bits] == NULL)
50  @throw [OFInvalidFormatException exception];
51 
52  iter = iter->leaves[bits];
53  }
54 
55  *value = iter->value;
56  return true;
57 }
58 
59 #ifdef __cplusplus
60 extern "C" {
61 #endif
62 extern OFHuffmanTree _Nonnull _OFHuffmanTreeNew(uint8_t lengths[_Nonnull],
63  uint16_t count) OF_VISIBILITY_HIDDEN;
64 extern OFHuffmanTree _Nonnull _OFHuffmanTreeNewSingle(uint16_t value)
65  OF_VISIBILITY_HIDDEN;
66 extern void _OFHuffmanTreeFree(OFHuffmanTree _Nonnull tree)
67  OF_VISIBILITY_HIDDEN;
68 #ifdef __cplusplus
69 }
70 #endif
71 
72 OF_ASSUME_NONNULL_END
An exception indicating that the format is invalid.
Definition: OFInvalidFormatException.h:29