Differences From Artifact [c8d56de598]:
- File src/huffman_tree.m — part of check-in [374e1a1bfa] at 2021-01-02 22:04:26 on branch trunk — Update copyright (user: js, size: 2672) [annotate] [blame] [check-ins using] [more...]
To Artifact [f7a4f8d9de]:
- File
src/OFHuffmanTree.m
— part of check-in
[2fcf5a3052]
at
2021-04-29 23:24:22
on branch trunk
— Clean up struct and enum typedefs
With TYPEDEF_HIDES_STRUCT set, Doxygen properly handles anonymous
structs and enums that are typedef'd. (user: js, size: 2592) [annotate] [blame] [check-ins using] [more...]
︙ | ︙ | |||
14 15 16 17 18 19 20 | */ #include "config.h" #include <stdint.h> #include <stdlib.h> | | | | | | < | | | | | | 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 | */ #include "config.h" #include <stdint.h> #include <stdlib.h> #import "OFHuffmanTree.h" #import "OFInvalidFormatException.h" #import "OFOutOfMemoryException.h" static OFHuffmanTree newTree(void) { OFHuffmanTree tree; tree = OFAllocMemory(1, sizeof(*tree)); tree->leaves[0] = tree->leaves[1] = NULL; tree->value = 0xFFFF; return tree; } static void treeInsert(OFHuffmanTree tree, uint16_t code, uint8_t length, uint16_t value) { while (length > 0) { uint8_t bit; length--; bit = (code & (1u << length)) >> length; if (tree->leaves[bit] == NULL) tree->leaves[bit] = newTree(); tree = tree->leaves[bit]; } tree->value = value; } OFHuffmanTree OFHuffmanTreeNew(uint8_t lengths[], uint16_t count) { OFHuffmanTree tree; uint16_t *lengthCount = NULL; uint16_t code, maxCode = 0, *nextCode = NULL; uint_fast8_t maxBit = 0; @try { for (uint16_t i = 0; i < count; i++) { uint_fast8_t length = lengths[i]; if OF_UNLIKELY (length > maxBit) { lengthCount = OFResizeMemory(lengthCount, length + 1, sizeof(uint16_t)); nextCode = OFResizeMemory(nextCode, length + 1, sizeof(uint16_t)); for (uint_fast8_t j = maxBit + 1; j <= length; j++) { lengthCount[j] = 0; nextCode[j] = 0; } |
︙ | ︙ | |||
95 96 97 98 99 100 101 | tree = newTree(); for (uint16_t i = 0; i <= maxCode; i++) { uint8_t length = lengths[i]; if (length > 0) | | | | | | | | | | | 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 | tree = newTree(); for (uint16_t i = 0; i <= maxCode; i++) { uint8_t length = lengths[i]; if (length > 0) treeInsert(tree, nextCode[length]++, length, i); } } @finally { OFFreeMemory(lengthCount); OFFreeMemory(nextCode); } return tree; } OFHuffmanTree OFHuffmanTreeNewSingle(uint16_t value) { OFHuffmanTree tree = newTree(); tree->value = value; return tree; } void OFHuffmanTreeFree(OFHuffmanTree tree) { for (uint_fast8_t i = 0; i < 2; i++) if OF_LIKELY (tree->leaves[i] != NULL) OFHuffmanTreeFree(tree->leaves[i]); OFFreeMemory(tree); } |