Mercurial > libavcodec.hg
annotate lzwenc.c @ 11352:6e0af2cfdcfe libavcodec
Do MC and IDCT in coding (hilbert) order
This increases the slice size to 64 pixels, due to having to decode an
entire chroma superblock row per slice.
This can be up to 6% slower depending on clip and CPU, but is necessary
for future optimizations that gain significantly more than was lost.
author | conrad |
---|---|
date | Wed, 03 Mar 2010 23:27:40 +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 } |