source: sandbox/JamPlayerUSB/jbicomp.c

Last change on this file was 109, checked in by demin, 14 years ago

First working version
File size: 6.0 KB
Line 
1/****************************************************************************/
2/* */
3/* Module: jbicomp.c */
4/* */
5/* Copyright (C) Altera Corporation 1997-2001 */
6/* */
7/* Description: Contains the code for compressing and uncompressing */
8/* Boolean array data. */
9/* */
10/* This algorithm works by searching previous bytes in the */
11/* data that match the current data. If a match is found, */
12/* then the offset and length of the matching data can */
13/* replace the actual data in the output. */
14/* */
15/* Revisions: 2.2 fixed /W4 warnings */
16/* */
17/****************************************************************************/
18
19#include "jbiexprt.h"
20#include "jbicomp.h"
21
22#define SHORT_BITS 16
23#define CHAR_BITS 8
24#define DATA_BLOB_LENGTH 3
25#define MATCH_DATA_LENGTH 8192
26#define JBI_ACA_REQUEST_SIZE 1024
27#define JBI_ACA_BUFFER_SIZE (MATCH_DATA_LENGTH + JBI_ACA_REQUEST_SIZE)
28
29unsigned long jbi_in_length = 0L;
30unsigned long jbi_in_index = 0L; /* byte index into compressed array */
31unsigned int jbi_bits_avail = CHAR_BITS;
32
33/****************************************************************************/
34/* */
35/* The following functions implement incremental decompression of Boolean */
36/* array data, using a small memory window. */
37/* */
38/* This algorithm works by searching previous bytes in the data that match */
39/* the current data. If a match is found, then the offset and length of */
40/* the matching data can replace the actual data in the output. */
41/* */
42/* Memory usage is reduced by maintaining a "window" buffer which contains */
43/* the uncompressed data for one 8K page, plus some extra amount specified */
44/* by JBI_ACA_REQUEST_SIZE. The function jbi_uncompress_page() is used to */
45/* request a subrange of the uncompressed data, starting at a particular */
46/* bit position and extending a maximum of JBI_ACA_REQUEST_SIZE bytes. */
47/* */
48/****************************************************************************/
49
50/****************************************************************************/
51/* */
52
53unsigned int jbi_bits_required(unsigned int n)
54
55/* */
56/* Description: Calculate the minimum number of bits required to */
57/* represent n. */
58/* */
59/* Returns: Number of bits. */
60/* */
61/****************************************************************************/
62{
63 unsigned int result = SHORT_BITS;
64
65 if (n == 0)
66 {
67 result = 1;
68 }
69 else
70 {
71 /* Look for the highest non-zero bit position */
72 while ((n & (1 << (SHORT_BITS - 1))) == 0)
73 {
74 n <<= 1;
75 --result;
76 }
77 }
78
79 return (result);
80}
81
82/****************************************************************************/
83/* */
84
85unsigned int jbi_read_packed
86(
87 unsigned char *buffer,
88 unsigned int bits
89)
90
91/* */
92/* Description: Read the next value from the input array "buffer". */
93/* Read only "bits" bits from the array. The amount of */
94/* bits that have already been read from "buffer" is */
95/* stored internally to this function. */
96/* */
97/* Returns: Up to 16 bit value. -1 if buffer overrun. */
98/* */
99/****************************************************************************/
100{
101 unsigned int result = 0;
102 unsigned int shift = 0;
103 unsigned int databyte = 0;
104
105 while (bits > 0)
106 {
107
108 databyte = buffer[jbi_in_index];
109 result |= (((databyte >> (CHAR_BITS - jbi_bits_avail))
110 & (0xFF >> (CHAR_BITS - jbi_bits_avail))) << shift);
111
112 if (bits <= jbi_bits_avail)
113 {
114 result &= (0xFFFF >> (SHORT_BITS - (bits + shift)));
115 jbi_bits_avail -= bits;
116 bits = 0;
117 }
118 else
119 {
120 ++jbi_in_index;
121 shift += jbi_bits_avail;
122 bits -= jbi_bits_avail;
123 jbi_bits_avail = CHAR_BITS;
124 }
125 }
126
127 return (result);
128}
129
130/****************************************************************************/
131/* */
132
133unsigned long jbi_uncompress
134(
135 unsigned char *in,
136 unsigned long in_length,
137 unsigned char *out,
138 unsigned long out_length,
139 int version
140)
141
142/* */
143/* Description: Uncompress data in "in" and write result to "out". */
144/* */
145/* Returns: Length of uncompressed data. -1 if: */
146/* 1) out_length is too small */
147/* 2) Internal error in the code */
148/* 3) in doesn't contain ACA compressed data. */
149/* */
150/****************************************************************************/
151{
152 unsigned long i, j, data_length = 0L;
153 unsigned int offset, length;
154 unsigned int match_data_length = MATCH_DATA_LENGTH;
155
156 if (version > 0) --match_data_length;
157
158 jbi_in_length = in_length;
159 jbi_bits_avail = CHAR_BITS;
160 jbi_in_index = 0L;
161 for (i = 0; i < out_length; ++i) out[i] = 0;
162
163 /* Read number of bytes in data. */
164 for (i = 0; i < sizeof (in_length); ++i)
165 {
166 data_length = data_length | ((unsigned long)
167 jbi_read_packed(in, CHAR_BITS) << (i * CHAR_BITS));
168 }
169
170 if (data_length > out_length)
171 {
172 data_length = 0L;
173 }
174 else
175 {
176 i = 0;
177 while (i < data_length)
178 {
179 /* A 0 bit indicates literal data. */
180 if (jbi_read_packed(in, 1) == 0)
181 {
182 for (j = 0; j < DATA_BLOB_LENGTH; ++j)
183 {
184 if (i < data_length)
185 {
186 out[i] = (unsigned char) jbi_read_packed(in, CHAR_BITS);
187 i++;
188 }
189 }
190 }
191 else
192 {
193 /* A 1 bit indicates offset/length to follow. */
194 offset = jbi_read_packed(in, jbi_bits_required((short) (i > match_data_length ? match_data_length : i)));
195 length = jbi_read_packed(in, CHAR_BITS);
196
197 for (j = 0; j < length; ++j)
198 {
199 if (i < data_length)
200 {
201 out[i] = out[i - offset];
202 i++;
203 }
204 }
205 }
206 }
207 }
208
209 return (data_length);
210}
211
Note: See TracBrowser for help on using the repository browser.