Differences From Artifact [d14cb85d84]:
- File
src/huffman_tree.m
— part of check-in
[44413ada84]
at
2018-06-03 20:11:18
on branch trunk
— Work around GCC being extremely buggy
This includes GCC thinking uint16_t and uint_fast16_t have a different
signedness and pointers to subclasses of OFStream and pointers to
OFStream being incompatible pointer types. (user: js, size: 3032) [annotate] [blame] [check-ins using]
To Artifact [fc3617ec1a]:
- File
src/huffman_tree.m
— part of check-in
[e9398866eb]
at
2018-12-01 21:06:48
on branch trunk
— huffman_tree.m: Do not limit codes to 15 bit
This limitation is only present in DEFLATE, LHA does not have this
limitation. (user: js, size: 3547) [annotate] [blame] [check-ins using]
| ︙ | ︙ | |||
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)
|
| ︙ | ︙ |