Overview
Comment: | huffman_tree.m: Do not limit codes to 15 bit
This limitation is only present in DEFLATE, LHA does not have this |
---|---|
Downloads: | Tarball | ZIP archive | SQL archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA3-256: |
e9398866eb6fd745f2040891d9764e76 |
User & Date: | js on 2018-12-01 21:06:48 |
Other Links: | manifest | tags |
Context
2018-12-01
| ||
21:32 | ofarc: Fix a typo check-in: e62556c4a5 user: js tags: trunk | |
21:06 | huffman_tree.m: Do not limit codes to 15 bit check-in: e9398866eb user: js tags: trunk | |
19:33 | ObjFW.h: Fix unicode.h import check-in: f1e2e08017 user: js tags: trunk | |
Changes
Modified src/huffman_tree.m from [d14cb85d84] to [fc3617ec1a].
︙ | ︙ | |||
21 22 23 24 25 26 27 | #include <stdlib.h> #import "huffman_tree.h" #import "OFInvalidFormatException.h" #import "OFOutOfMemoryException.h" | < < | 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | #include <stdlib.h> #import "huffman_tree.h" #import "OFInvalidFormatException.h" #import "OFOutOfMemoryException.h" static struct of_huffman_tree * newTree(void) { struct of_huffman_tree *tree; if ((tree = malloc(sizeof(*tree))) == NULL) @throw [OFOutOfMemoryException |
︙ | ︙ | |||
61 62 63 64 65 66 67 | tree->value = value; } struct of_huffman_tree * of_huffman_tree_construct(uint8_t lengths[], uint16_t count) { struct of_huffman_tree *tree; | | | | < > | | | > > | > > > > > > > > > > > > > > > > > > > > | | | | | | | | | | | | | | | > > > > | 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 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 | tree->value = value; } struct of_huffman_tree * of_huffman_tree_construct(uint8_t lengths[], uint16_t count) { struct of_huffman_tree *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) { size_t size = (length + 1) * sizeof(uint16_t); uint16_t *new; if ((new = realloc(lengthCount, size)) == NULL) @throw [OFOutOfMemoryException exceptionWithRequestedSize: size]; lengthCount = new; if ((new = realloc(nextCode, size)) == NULL) @throw [OFOutOfMemoryException exceptionWithRequestedSize: size]; nextCode = new; for (uint_fast8_t j = maxBit + 1; j <= length; j++) { lengthCount[j] = 0; nextCode[j] = 0; } maxBit = length; } if (length > 0) { lengthCount[length]++; maxCode = i; } } code = 0; for (size_t i = 1; i <= maxBit; i++) { code = (code + lengthCount[i - 1]) << 1; nextCode[i] = code; } tree = newTree(); for (uint16_t i = 0; i <= maxCode; i++) { uint8_t length = lengths[i]; if (length > 0) insertTree(tree, nextCode[length]++, length, i); } } @finally { free(lengthCount); free(nextCode); } return tree; } struct of_huffman_tree * of_huffman_tree_construct_single(uint16_t value) |
︙ | ︙ |