Mercurial > libavcodec.hg
annotate lzwenc.c @ 10680:d569841bd1b7 libavcodec
Clarify comment: although still hacky, it is correct for existing libtheora
author | conrad |
---|---|
date | Sat, 12 Dec 2009 20:18:49 +0000 |
parents | e15eb76d9e47 |
children | 7dd2a45249a9 |
rev | line source |
---|---|
4798
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
1 /* |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
2 * LZW encoder |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
3 * Copyright (c) 2007 Bartlomiej Wolowiec |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
4 * |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
5 * This file is part of FFmpeg. |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
6 * |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
7 * FFmpeg is free software; you can redistribute it and/or |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
8 * modify it under the terms of the GNU Lesser General Public |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
9 * License as published by the Free Software Foundation; either |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
10 * version 2.1 of the License, or (at your option) any later version. |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
11 * |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
12 * FFmpeg is distributed in the hope that it will be useful, |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
15 * Lesser General Public License for more details. |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
16 * |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
17 * You should have received a copy of the GNU Lesser General Public |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
18 * License along with FFmpeg; if not, write to the Free Software |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
20 */ |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
21 |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
22 /** |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
23 * LZW encoder |
8718
e9d9d946f213
Use full internal pathname in doxygen @file directives.
diego
parents:
4833
diff
changeset
|
24 * @file libavcodec/lzwenc.c |
4798
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
25 * @author Bartlomiej Wolowiec |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
26 */ |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
27 |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
28 #include "avcodec.h" |
9411
4cb7c65fc775
Split bitstream.h, put the bitstream writer stuff in the new file
stefano
parents:
9178
diff
changeset
|
29 #include "put_bits.h" |
4798
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
30 #include "lzw.h" |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
31 |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
32 #define LZW_MAXBITS 12 |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
33 #define LZW_SIZTABLE (1<<LZW_MAXBITS) |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
34 #define LZW_HASH_SIZE 16411 |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
35 #define LZW_HASH_SHIFT 6 |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
36 |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
37 #define LZW_PREFIX_EMPTY -1 |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
38 #define LZW_PREFIX_FREE -2 |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
39 |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
40 /** One code in hash table */ |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
41 typedef struct Code{ |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
42 /// Hash code of prefix, LZW_PREFIX_EMPTY if empty prefix, or LZW_PREFIX_FREE if no code |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
43 int hash_prefix; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
44 int code; ///< LZW code |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
45 uint8_t suffix; ///< Last character in code block |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
46 }Code; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
47 |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
48 /** LZW encode state */ |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
49 typedef struct LZWEncodeState { |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
50 int clear_code; ///< Value of clear code |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
51 int end_code; ///< Value of end code |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
52 Code tab[LZW_HASH_SIZE]; ///< Hash table |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
53 int tabsize; ///< Number of values in hash table |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
54 int bits; ///< Actual bits code |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
55 int bufsize; ///< Size of output buffer |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
56 PutBitContext pb; ///< Put bit context for output |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
57 int maxbits; ///< Max bits code |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
58 int maxcode; ///< Max value of code |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
59 int output_bytes; ///< Number of written bytes |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
60 int last_code; ///< Value of last output code or LZW_PREFIX_EMPTY |
10634 | 61 enum FF_LZW_MODES mode; ///< TIFF or GIF |
62 void (*put_bits)(PutBitContext *, int, unsigned); ///< GIF is LE while TIFF is BE | |
4798
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
63 }LZWEncodeState; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
64 |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
65 |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
66 const int ff_lzw_encode_state_size = sizeof(LZWEncodeState); |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
67 |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
68 /** |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
69 * Hash function adding character |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
70 * @param head LZW code for prefix |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
71 * @param add Character to add |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
72 * @return New hash value |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
73 */ |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
74 static inline int hash(int head, const int add) |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
75 { |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
76 head ^= (add << LZW_HASH_SHIFT); |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
77 if (head >= LZW_HASH_SIZE) |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
78 head -= LZW_HASH_SIZE; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
79 assert(head >= 0 && head < LZW_HASH_SIZE); |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
80 return head; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
81 } |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
82 |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
83 /** |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
84 * Hash function calculates next hash value |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
85 * @param head Actual hash code |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
86 * @param offset Offset calculated by hashOffset |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
87 * @return New hash value |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
88 */ |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
89 static inline int hashNext(int head, const int offset) |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
90 { |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
91 head -= offset; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
92 if(head < 0) |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
93 head += LZW_HASH_SIZE; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
94 return head; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
95 } |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
96 |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
97 /** |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
98 * Hash function calculates hash offset |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
99 * @param head Actual hash code |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
100 * @return Hash offset |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
101 */ |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
102 static inline int hashOffset(const int head) |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
103 { |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
104 return head ? LZW_HASH_SIZE - head : 1; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
105 } |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
106 |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
107 /** |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
108 * Write one code to stream |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
109 * @param s LZW state |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
110 * @param c code to write |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
111 */ |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
112 static inline void writeCode(LZWEncodeState * s, int c) |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
113 { |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
114 assert(0 <= c && c < 1 << s->bits); |
10634 | 115 s->put_bits(&s->pb, s->bits, c); |
4798
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
116 } |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
117 |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
118 |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
119 /** |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
120 * Find LZW code for block |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
121 * @param s LZW state |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
122 * @param c Last character in block |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
123 * @param hash_prefix LZW code for prefix |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
124 * @return LZW code for block or -1 if not found in table |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
125 */ |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
126 static inline int findCode(LZWEncodeState * s, uint8_t c, int hash_prefix) |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
127 { |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
128 int h = hash(FFMAX(hash_prefix, 0), c); |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
129 int hash_offset = hashOffset(h); |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
130 |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
131 while (s->tab[h].hash_prefix != LZW_PREFIX_FREE) { |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
132 if ((s->tab[h].suffix == c) |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
133 && (s->tab[h].hash_prefix == hash_prefix)) |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
134 return h; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
135 h = hashNext(h, hash_offset); |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
136 } |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
137 |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
138 return h; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
139 } |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
140 |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
141 /** |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
142 * Add block to LZW code table |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
143 * @param s LZW state |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
144 * @param c Last character in block |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
145 * @param hash_prefix LZW code for prefix |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
146 * @param hash_code LZW code for bytes block |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
147 */ |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
148 static inline void addCode(LZWEncodeState * s, uint8_t c, int hash_prefix, int hash_code) |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
149 { |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
150 s->tab[hash_code].code = s->tabsize; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
151 s->tab[hash_code].suffix = c; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
152 s->tab[hash_code].hash_prefix = hash_prefix; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
153 |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
154 s->tabsize++; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
155 |
10634 | 156 if (s->tabsize >= (1 << s->bits) + (s->mode == FF_LZW_GIF)) |
4798
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
157 s->bits++; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
158 } |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
159 |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
160 /** |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
161 * Clear LZW code table |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
162 * @param s LZW state |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
163 */ |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
164 static void clearTable(LZWEncodeState * s) |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
165 { |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
166 int i, h; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
167 |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
168 writeCode(s, s->clear_code); |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
169 s->bits = 9; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
170 for (i = 0; i < LZW_HASH_SIZE; i++) { |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
171 s->tab[i].hash_prefix = LZW_PREFIX_FREE; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
172 } |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
173 for (i = 0; i < 256; i++) { |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
174 h = hash(0, i); |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
175 s->tab[h].code = i; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
176 s->tab[h].suffix = i; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
177 s->tab[h].hash_prefix = LZW_PREFIX_EMPTY; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
178 } |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
179 s->tabsize = 258; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
180 } |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
181 |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
182 /** |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
183 * Calculate number of bytes written |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
184 * @param s LZW encode state |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
185 * @return Number of bytes written |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
186 */ |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
187 static int writtenBytes(LZWEncodeState *s){ |
4833 | 188 int ret = put_bits_count(&s->pb) >> 3; |
4798
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
189 ret -= s->output_bytes; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
190 s->output_bytes += ret; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
191 return ret; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
192 } |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
193 |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
194 /** |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
195 * Initialize LZW encoder. Please set s->clear_code, s->end_code and s->maxbits before run. |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
196 * @param s LZW state |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
197 * @param outbuf Output buffer |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
198 * @param outsize Size of output buffer |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
199 * @param maxbits Maximum length of code |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
200 */ |
10634 | 201 void ff_lzw_encode_init(LZWEncodeState *s, uint8_t *outbuf, int outsize, |
202 int maxbits, enum FF_LZW_MODES mode, | |
203 void (*lzw_put_bits)(PutBitContext *, int, unsigned)) | |
4798
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
204 { |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
205 s->clear_code = 256; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
206 s->end_code = 257; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
207 s->maxbits = maxbits; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
208 init_put_bits(&s->pb, outbuf, outsize); |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
209 s->bufsize = outsize; |
9178 | 210 assert(s->maxbits >= 9 && s->maxbits <= LZW_MAXBITS); |
4798
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
211 s->maxcode = 1 << s->maxbits; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
212 s->output_bytes = 0; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
213 s->last_code = LZW_PREFIX_EMPTY; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
214 s->bits = 9; |
10634 | 215 s->mode = mode; |
216 s->put_bits = lzw_put_bits; | |
4798
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
217 } |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
218 |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
219 /** |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
220 * LZW main compress function |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
221 * @param s LZW state |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
222 * @param inbuf Input buffer |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
223 * @param insize Size of input buffer |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
224 * @return Number of bytes written or -1 on error |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
225 */ |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
226 int ff_lzw_encode(LZWEncodeState * s, const uint8_t * inbuf, int insize) |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
227 { |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
228 int i; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
229 |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
230 if(insize * 3 > (s->bufsize - s->output_bytes) * 2){ |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
231 return -1; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
232 } |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
233 |
4832 | 234 if (s->last_code == LZW_PREFIX_EMPTY) |
4798
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
235 clearTable(s); |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
236 |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
237 for (i = 0; i < insize; i++) { |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
238 uint8_t c = *inbuf++; |
4832 | 239 int code = findCode(s, c, s->last_code); |
4831 | 240 if (s->tab[code].hash_prefix == LZW_PREFIX_FREE) { |
4832 | 241 writeCode(s, s->last_code); |
242 addCode(s, c, s->last_code, code); | |
4831 | 243 code= hash(0, c); |
4798
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
244 } |
4832 | 245 s->last_code = s->tab[code].code; |
4798
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
246 if (s->tabsize >= s->maxcode - 1) { |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
247 clearTable(s); |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
248 } |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
249 } |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
250 |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
251 return writtenBytes(s); |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
252 } |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
253 |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
254 /** |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
255 * Write end code and flush bitstream |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
256 * @param s LZW state |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
257 * @return Number of bytes written or -1 on error |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
258 */ |
10634 | 259 int ff_lzw_encode_flush(LZWEncodeState *s, |
260 void (*lzw_flush_put_bits)(PutBitContext *)) | |
4798
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
261 { |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
262 if (s->last_code != -1) |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
263 writeCode(s, s->last_code); |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
264 writeCode(s, s->end_code); |
10634 | 265 lzw_flush_put_bits(&s->pb); |
4798
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
266 s->last_code = -1; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
267 |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
268 return writtenBytes(s); |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
269 } |