ObjFW
huffman_tree.h
1 /*
2  * Copyright (c) 2008-2021 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 struct of_huffman_tree {
26  struct of_huffman_tree *_Nullable leaves[2];
27  uint16_t value;
28 };
29 
30 static OF_INLINE bool
31 of_huffman_tree_walk(id _Nullable stream,
32  bool (*bitReader)(id _Nullable, uint16_t *_Nonnull, uint8_t),
33  struct of_huffman_tree *_Nonnull *_Nonnull tree, uint16_t *_Nonnull value)
34 {
35  struct of_huffman_tree *iter = *tree;
36  uint16_t bits;
37 
38  while (iter->value == 0xFFFF) {
39  if OF_UNLIKELY (!bitReader(stream, &bits, 1)) {
40  *tree = iter;
41  return false;
42  }
43 
44  if OF_UNLIKELY (iter->leaves[bits] == NULL)
45  @throw [OFInvalidFormatException exception];
46 
47  iter = iter->leaves[bits];
48  }
49 
50  *value = iter->value;
51  return true;
52 }
53 
54 #ifdef __cplusplus
55 extern "C" {
56 #endif
57 extern struct of_huffman_tree *_Nonnull of_huffman_tree_construct(
58  uint8_t lengths[_Nonnull], uint16_t count);
59 extern struct of_huffman_tree *_Nonnull of_huffman_tree_construct_single(
60  uint16_t value);
61 extern void of_huffman_tree_release(struct of_huffman_tree *_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:27