annotate lzwenc.c @ 5297:fc46b3f5de1a libavcodec

indent
author mru
date Thu, 12 Jul 2007 22:55:35 +0000
parents cad24e81a7b4
children e9d9d946f213
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
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
cad24e81a7b4 superflouos ()
michael
parents: 4832
diff changeset
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
8a5cbe8e014e remove code_prefix variable, no speed change
michael
parents: 4831
diff changeset
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
8a5cbe8e014e remove code_prefix variable, no speed change
michael
parents: 4831
diff changeset
233 int code = findCode(s, c, s->last_code);
4831
4a7e1f5cdc7a simplify
michael
parents: 4798
diff changeset
234 if (s->tab[code].hash_prefix == LZW_PREFIX_FREE) {
4832
8a5cbe8e014e remove code_prefix variable, no speed change
michael
parents: 4831
diff changeset
235 writeCode(s, s->last_code);
8a5cbe8e014e remove code_prefix variable, no speed change
michael
parents: 4831
diff changeset
236 addCode(s, c, s->last_code, code);
4831
4a7e1f5cdc7a simplify
michael
parents: 4798
diff changeset
237 code= hash(0, c);
4798
c68b9a261f79 LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
michael
parents:
diff changeset
238 }
4832
8a5cbe8e014e remove code_prefix variable, no speed change
michael
parents: 4831
diff changeset
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 }