Mercurial > libavcodec.hg
annotate lzwenc.c @ 5508:07cd560e9a8c libavcodec
debug: tell how much bits are skipped with unknown nal code
author | alex |
---|---|
date | Wed, 08 Aug 2007 20:27:18 +0000 |
parents | cad24e81a7b4 |
children | e9d9d946f213 |
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 |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
24 * @file lzwenc.c |
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" |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
29 #include "bitstream.h" |
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 |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
61 }LZWEncodeState; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
62 |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
63 |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
64 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
|
65 |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
66 /** |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
67 * Hash function adding character |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
68 * @param head LZW code for prefix |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
69 * @param add Character to add |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
70 * @return New hash value |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
71 */ |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
72 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
|
73 { |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
74 head ^= (add << LZW_HASH_SHIFT); |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
75 if (head >= LZW_HASH_SIZE) |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
76 head -= LZW_HASH_SIZE; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
77 assert(head >= 0 && head < LZW_HASH_SIZE); |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
78 return head; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
79 } |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
80 |
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 * Hash function calculates next hash value |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
83 * @param head Actual hash code |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
84 * @param offset Offset calculated by hashOffset |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
85 * @return New hash value |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
86 */ |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
87 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
|
88 { |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
89 head -= offset; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
90 if(head < 0) |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
91 head += LZW_HASH_SIZE; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
92 return head; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
93 } |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
94 |
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 * Hash function calculates hash offset |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
97 * @param head Actual hash code |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
98 * @return Hash offset |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
99 */ |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
100 static inline int hashOffset(const int head) |
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 return head ? LZW_HASH_SIZE - head : 1; |
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 |
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 * Write one code to stream |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
107 * @param s LZW state |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
108 * @param c code to write |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
109 */ |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
110 static inline void writeCode(LZWEncodeState * s, int c) |
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 assert(0 <= c && c < 1 << s->bits); |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
113 put_bits(&s->pb, s->bits, c); |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
114 } |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
115 |
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 * Find LZW code for block |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
119 * @param s LZW state |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
120 * @param c Last character in block |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
121 * @param hash_prefix LZW code for prefix |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
122 * @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
|
123 */ |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
124 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
|
125 { |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
126 int h = hash(FFMAX(hash_prefix, 0), c); |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
127 int hash_offset = hashOffset(h); |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
128 |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
129 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
|
130 if ((s->tab[h].suffix == c) |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
131 && (s->tab[h].hash_prefix == hash_prefix)) |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
132 return h; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
133 h = hashNext(h, hash_offset); |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
134 } |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
135 |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
136 return h; |
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 |
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 * Add block to LZW code table |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
141 * @param s LZW state |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
142 * @param c Last character in block |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
143 * @param hash_prefix LZW code for prefix |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
144 * @param hash_code LZW code for bytes block |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
145 */ |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
146 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
|
147 { |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
148 s->tab[hash_code].code = s->tabsize; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
149 s->tab[hash_code].suffix = c; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
150 s->tab[hash_code].hash_prefix = hash_prefix; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
151 |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
152 s->tabsize++; |
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 if (s->tabsize >= 1 << s->bits) |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
155 s->bits++; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
156 } |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
157 |
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 * Clear LZW code table |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
160 * @param s LZW state |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
161 */ |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
162 static void clearTable(LZWEncodeState * s) |
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 int i, h; |
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 writeCode(s, s->clear_code); |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
167 s->bits = 9; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
168 for (i = 0; i < LZW_HASH_SIZE; i++) { |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
169 s->tab[i].hash_prefix = LZW_PREFIX_FREE; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
170 } |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
171 for (i = 0; i < 256; i++) { |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
172 h = hash(0, i); |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
173 s->tab[h].code = i; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
174 s->tab[h].suffix = i; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
175 s->tab[h].hash_prefix = LZW_PREFIX_EMPTY; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
176 } |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
177 s->tabsize = 258; |
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 |
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 * Calculate number of bytes written |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
182 * @param s LZW encode state |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
183 * @return Number of bytes written |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
184 */ |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
185 static int writtenBytes(LZWEncodeState *s){ |
4833 | 186 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
|
187 ret -= s->output_bytes; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
188 s->output_bytes += ret; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
189 return ret; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
190 } |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
191 |
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 * 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
|
194 * @param s LZW state |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
195 * @param outbuf Output buffer |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
196 * @param outsize Size of output buffer |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
197 * @param maxbits Maximum length of code |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
198 */ |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
199 void ff_lzw_encode_init(LZWEncodeState * s, uint8_t * outbuf, int outsize, int maxbits) |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
200 { |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
201 s->clear_code = 256; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
202 s->end_code = 257; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
203 s->maxbits = maxbits; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
204 init_put_bits(&s->pb, outbuf, outsize); |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
205 s->bufsize = outsize; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
206 assert(9 <= s->maxbits && s->maxbits <= s->maxbits); |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
207 s->maxcode = 1 << s->maxbits; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
208 s->output_bytes = 0; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
209 s->last_code = LZW_PREFIX_EMPTY; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
210 s->bits = 9; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
211 } |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
212 |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
213 /** |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
214 * LZW main compress function |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
215 * @param s LZW state |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
216 * @param inbuf Input buffer |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
217 * @param insize Size of input buffer |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
218 * @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
|
219 */ |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
220 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
|
221 { |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
222 int i; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
223 |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
224 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
|
225 return -1; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
226 } |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
227 |
4832 | 228 if (s->last_code == LZW_PREFIX_EMPTY) |
4798
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
229 clearTable(s); |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
230 |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
231 for (i = 0; i < insize; i++) { |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
232 uint8_t c = *inbuf++; |
4832 | 233 int code = findCode(s, c, s->last_code); |
4831 | 234 if (s->tab[code].hash_prefix == LZW_PREFIX_FREE) { |
4832 | 235 writeCode(s, s->last_code); |
236 addCode(s, c, s->last_code, code); | |
4831 | 237 code= hash(0, c); |
4798
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
238 } |
4832 | 239 s->last_code = s->tab[code].code; |
4798
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
240 if (s->tabsize >= s->maxcode - 1) { |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
241 clearTable(s); |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
242 } |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
243 } |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
244 |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
245 return writtenBytes(s); |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
246 } |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
247 |
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 * Write end code and flush bitstream |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
250 * @param s LZW state |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
251 * @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
|
252 */ |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
253 int ff_lzw_encode_flush(LZWEncodeState * s) |
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 if (s->last_code != -1) |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
256 writeCode(s, s->last_code); |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
257 writeCode(s, s->end_code); |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
258 flush_put_bits(&s->pb); |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
259 s->last_code = -1; |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
260 |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
261 return writtenBytes(s); |
c68b9a261f79
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff
changeset
|
262 } |