ObjFW
OFHuffmanTree.h
1 /*
2  * Copyright (c) 2008-2024 Jonathan Schleifer <js@nil.im>
3  *
4  * All rights reserved.
5  *
6  * This file is part of ObjFW. It may be distributed under the terms of the
7  * Q Public License 1.0, which can be found in the file LICENSE.QPL included in
8  * the packaging of this file.
9  *
10  * Alternatively, it may be distributed under the terms of the GNU General
11  * Public License, either version 2 or 3, which can be found in the file
12  * LICENSE.GPLv2 or LICENSE.GPLv3 respectively included in the packaging of this
13  * file.
14  */
15 
16 #include <stdbool.h>
17 #include <stdint.h>
18 
19 #import "macros.h"
20 
21 #import "OFInvalidFormatException.h"
22 
23 OF_ASSUME_NONNULL_BEGIN
24 
25 typedef struct _OFHuffmanTree {
26  struct _OFHuffmanTree *_Nullable leaves[2];
27  uint16_t value;
28 } *OFHuffmanTree;
29 
30 /* Inlined for performance. */
31 static OF_INLINE bool
32 OFHuffmanTreeWalk(id _Nullable stream,
33  bool (*bitReader)(id _Nullable, uint16_t *_Nonnull, uint8_t),
34  OFHuffmanTree _Nonnull *_Nonnull tree, uint16_t *_Nonnull value)
35 {
36  OFHuffmanTree iter = *tree;
37  uint16_t bits;
38 
39  while (iter->value == 0xFFFF) {
40  if OF_UNLIKELY (!bitReader(stream, &bits, 1)) {
41  *tree = iter;
42  return false;
43  }
44 
45  if OF_UNLIKELY (iter->leaves[bits] == NULL)
46  @throw [OFInvalidFormatException exception];
47 
48  iter = iter->leaves[bits];
49  }
50 
51  *value = iter->value;
52  return true;
53 }
54 
55 #ifdef __cplusplus
56 extern "C" {
57 #endif
58 extern OFHuffmanTree _Nonnull OFHuffmanTreeNew(uint8_t lengths[_Nonnull],
59  uint16_t count);
60 extern OFHuffmanTree _Nonnull OFHuffmanTreeNewSingle(uint16_t value);
61 extern void OFHuffmanTreeFree(OFHuffmanTree _Nonnull tree);
62 #ifdef __cplusplus
63 }
64 #endif
65 
66 OF_ASSUME_NONNULL_END
An exception indicating that the format is invalid.
Definition: OFInvalidFormatException.h:26