annotate lzwenc.c @ 11498:8e889ce0d616 libavcodec

100L, revert r22560, already present
author bcoudurier
date Mon, 15 Mar 2010 23:40:51 +0000
parents e15eb76d9e47
children 7dd2a45249a9
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
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
e15eb76d9e47 use lzw compression in gif encoder
bcoudurier
parents: 9411
diff changeset
61 enum FF_LZW_MODES mode; ///< TIFF or GIF
e15eb76d9e47 use lzw compression in gif encoder
bcoudurier
parents: 9411
diff changeset
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
e15eb76d9e47 use lzw compression in gif encoder
bcoudurier
parents: 9411
diff changeset
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
e15eb76d9e47 use lzw compression in gif encoder
bcoudurier
parents: 9411
diff changeset
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
cad24e81a7b4 superflouos ()
michael
parents: 4832
diff changeset
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
e15eb76d9e47 use lzw compression in gif encoder
bcoudurier
parents: 9411
diff changeset
201 void ff_lzw_encode_init(LZWEncodeState *s, uint8_t *outbuf, int outsize,
e15eb76d9e47 use lzw compression in gif encoder
bcoudurier
parents: 9411
diff changeset
202 int maxbits, enum FF_LZW_MODES mode,
e15eb76d9e47 use lzw compression in gif encoder
bcoudurier
parents: 9411
diff changeset
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
c1e6aaea75f2 Fix an assert().
benoit
parents: 8718
diff changeset
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
e15eb76d9e47 use lzw compression in gif encoder
bcoudurier
parents: 9411
diff changeset
215 s->mode = mode;
e15eb76d9e47 use lzw compression in gif encoder
bcoudurier
parents: 9411
diff changeset
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
8a5cbe8e014e remove code_prefix variable, no speed change
michael
parents: 4831
diff changeset
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
8a5cbe8e014e remove code_prefix variable, no speed change
michael
parents: 4831
diff changeset
239 int code = findCode(s, c, s->last_code);
4831
4a7e1f5cdc7a simplify
michael
parents: 4798
diff changeset
240 if (s->tab[code].hash_prefix == LZW_PREFIX_FREE) {
4832
8a5cbe8e014e remove code_prefix variable, no speed change
michael
parents: 4831
diff changeset
241 writeCode(s, s->last_code);
8a5cbe8e014e remove code_prefix variable, no speed change
michael
parents: 4831
diff changeset
242 addCode(s, c, s->last_code, code);
4831
4a7e1f5cdc7a simplify
michael
parents: 4798
diff changeset
243 code= hash(0, c);
4798
c68b9a261f79 LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff changeset
244 }
4832
8a5cbe8e014e remove code_prefix variable, no speed change
michael
parents: 4831
diff changeset
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
e15eb76d9e47 use lzw compression in gif encoder
bcoudurier
parents: 9411
diff changeset
259 int ff_lzw_encode_flush(LZWEncodeState *s,
e15eb76d9e47 use lzw compression in gif encoder
bcoudurier
parents: 9411
diff changeset
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
e15eb76d9e47 use lzw compression in gif encoder
bcoudurier
parents: 9411
diff changeset
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 }