PandA-2024.02
huffman.c
Go to the documentation of this file.
1 /*
2 +--------------------------------------------------------------------------+
3 | CHStone : a suite of benchmark programs for C-based High-Level Synthesis |
4 | ======================================================================== |
5 | |
6 | * Collected and Modified : Y. Hara, H. Tomiyama, S. Honda, |
7 | H. Takada and K. Ishii |
8 | Nagoya University, Japan |
9 | |
10 | * Remark : |
11 | 1. This source code is modified to unify the formats of the benchmark |
12 | programs in CHStone. |
13 | 2. Test vectors are added for CHStone. |
14 | 3. If "main_result" is 0 at the end of the program, the program is |
15 | correctly executed. |
16 | 4. Please follow the copyright of each benchmark program. |
17 +--------------------------------------------------------------------------+
18 */
19 /*
20  * Huffman decoding module
21  *
22  * @(#) $Id: huffman.c,v 1.2 2003/07/18 10:19:21 honda Exp $
23  */
24 
25 /*************************************************************
26 Copyright (C) 1990, 1991, 1993 Andy C. Hung, all rights reserved.
27 PUBLIC DOMAIN LICENSE: Stanford University Portable Video Research
28 Group. If you use this software, you agree to the following: This
29 program package is purely experimental, and is licensed "as is".
30 Permission is granted to use, modify, and distribute this program
31 without charge for any purpose, provided this license/ disclaimer
32 notice appears in the copies. No warranty or maintenance is given,
33 either expressed or implied. In no event shall the author(s) be
34 liable to you or a third party for any special, incidental,
35 consequential, or other damages, arising out of the use or inability
36 to use the program for any purpose (or the loss of data), even if we
37 have been advised of such possibilities. Any public reference or
38 advertisement of this source code should refer to it as the Portable
39 Video Research Group (PVRG) code, and not by any author(s) (or
40 Stanford University) name.
41 *************************************************************/
42 /*
43 ************************************************************
44 huffman.c
45 
46 This file represents the core Huffman routines, most of them
47 implemented with the JPEG reference. These routines are not very fast
48 and can be improved, but comprise very little of software run-time.
49 
50 ************************************************************
51 */
52 
53 /* Used for sign extensions. */
54 const static int extend_mask[20] = {
55  0xFFFFFFFE, 0xFFFFFFFC, 0xFFFFFFF8, 0xFFFFFFF0, 0xFFFFFFE0, 0xFFFFFFC0,
56  0xFFFFFF80, 0xFFFFFF00, 0xFFFFFE00, 0xFFFFFC00, 0xFFFFF800, 0xFFFFF000,
57  0xFFFFE000, 0xFFFFC000, 0xFFFF8000, 0xFFFF0000, 0xFFFE0000, 0xFFFC0000,
58  0xFFF80000, 0xFFF00000
59 };
60 
61 
62 /* Masks */
63 const int bit_set_mask[32] = { /* This is 2^i at ith position */
64  0x00000001, 0x00000002, 0x00000004, 0x00000008,
65  0x00000010, 0x00000020, 0x00000040, 0x00000080,
66  0x00000100, 0x00000200, 0x00000400, 0x00000800,
67  0x00001000, 0x00002000, 0x00004000, 0x00008000,
68  0x00010000, 0x00020000, 0x00040000, 0x00080000,
69  0x00100000, 0x00200000, 0x00400000, 0x00800000,
70  0x01000000, 0x02000000, 0x04000000, 0x08000000,
71  0x10000000, 0x20000000, 0x40000000, 0x80000000
72 };
73 
74 const int lmask[32] = { /* This is 2^{i+1}-1 */
75  0x00000001, 0x00000003, 0x00000007, 0x0000000f,
76  0x0000001f, 0x0000003f, 0x0000007f, 0x000000ff,
77  0x000001ff, 0x000003ff, 0x000007ff, 0x00000fff,
78  0x00001fff, 0x00003fff, 0x00007fff, 0x0000ffff,
79  0x0001ffff, 0x0003ffff, 0x0007ffff, 0x000fffff,
80  0x001fffff, 0x003fffff, 0x007fffff, 0x00ffffff,
81  0x01ffffff, 0x03ffffff, 0x07ffffff, 0x0fffffff,
82  0x1fffffff, 0x3fffffff, 0x7fffffff, 0xffffffff
83 };
84 
85 static unsigned int current_read_byte;
86 static int read_position = -1;
87 
88 /*
89  * pgetc() gets a character onto the stream but it checks to see
90  * if there are any marker conflicts.
91  */
92 static int
94 {
95  int temp;
96 
97  if ((temp = *CurHuffReadBuf++) == MARKER_MARKER)
98  { /* If MARKER then */
99  if ((temp = *CurHuffReadBuf++))
100  { /* if next is not 0xff, then marker */
101  printf ("Unanticipated marker detected.\n");
102  }
103  else
104  {
105  return (MARKER_MARKER);
106  }
107  }
108  return (temp);
109 }
110 
111 
112 /*
113  * buf_getb() gets a bit from the read stream.
114  */
115 int
117 {
118  if (read_position < 0)
119  {
121  read_position = 7;
122  }
123 
125  {
126  return (1);
127  }
128  return (0);
129 }
130 
131 
132 /*
133  * megetv() gets n bits from the read stream and returns it.
134  *
135  */
136 int
137 buf_getv (int n)
138 {
139  int p, rv;
140 
141  n--;
142  p = n - read_position;
143  while (p > 0)
144  {
145  if (read_position > 23)
146  { /* If byte buffer contains almost entire word */
147  rv = (current_read_byte << p); /* Manipulate buffer */
148  current_read_byte = pgetc (); /* Change read bytes */
149 
150  rv |= (current_read_byte >> (8 - p));
151  read_position = 7 - p;
152  return (rv & lmask[n]);
153  /* Can return pending residual val */
154  }
156  read_position += 8; /* else shift in new information */
157  p -= 8;
158  }
159 
160  if (!p)
161  { /* If position is zero */
162  read_position = -1;
163  /* Can return current byte */
164  return (current_read_byte & lmask[n]);
165  }
166 
167  p = -p;
168  /* Else reverse position and shift */
169  read_position = p - 1;
170  return ((current_read_byte >> p) & lmask[n]);
171 }
172 
173 
174 
175 /*
176  * Create Table for decoding
177  */
178 int
179 huff_make_dhuff_tb (int *p_xhtbl_bits, int p_dhtbl_ml,
180  int *p_dhtbl_maxcode, int *p_dhtbl_mincode,
181  int *p_dhtbl_valptr)
182 {
183  int i, j, p, code, size, l;
184  int huffsize[257];
185  int huffcode[257];
186  int lastp;
187 
188  /*
189  * Get size
190  */
191  for (p = 0, i = 1; i < 17; i++)
192  {
193  for (j = 1; j <= p_xhtbl_bits[i]; j++)
194  {
195  huffsize[p++] = i;
196  }
197  }
198 
199  huffsize[p] = 0;
200  lastp = p;
201 
202  p = 0;
203  code = 0;
204  size = huffsize[0];
205  while (1)
206  {
207  do
208  {
209  huffcode[p++] = code++;
210  }
211  while ((huffsize[p] == size) && (p < 257));
212  /* Overflow Detection */
213  if (!huffsize[p])
214  { /* All finished. */
215  break;
216  }
217  do
218  {
219  /* Shift next code to expand prefix. */
220  code <<= 1;
221  size++;
222  }
223  while (huffsize[p] != size);
224  }
225 
226  for (p_dhtbl_ml = 1, p = 0, l = 1; l <= 16; l++)
227  {
228  if (p_xhtbl_bits[l] == 0)
229  {
230  p_dhtbl_maxcode[l] = -1; /* Watch out JPEG is wrong here */
231  }
232  else
233  { /* We use -1 to indicate skipping. */
234  p_dhtbl_valptr[l] = p;
235  p_dhtbl_mincode[l] = huffcode[p];
236  p += p_xhtbl_bits[l] - 1;
237  p_dhtbl_maxcode[l] = huffcode[p];
238  p_dhtbl_ml = l;
239  p++;
240  }
241  }
242  p_dhtbl_maxcode[p_dhtbl_ml]++;
243  return p_dhtbl_ml;
244 }
245 
246 
247 /*
248  *
249  */
250 int
251 DecodeHuffman (int *Xhuff_huffval, int Dhuff_ml,
252  int *Dhuff_maxcode, int *Dhuff_mincode, int *Dhuff_valptr)
253 {
254  int code, l, p;
255 
256  code = buf_getb ();
257  for (l = 1; code > Dhuff_maxcode[l]; l++)
258  {
259  code = (code << 1) + buf_getb ();
260  }
261 
262  if (code < Dhuff_maxcode[Dhuff_ml])
263  {
264  p = Dhuff_valptr[l] + code - Dhuff_mincode[l];
265  return (Xhuff_huffval[p]);
266  }
267  else
268  {
269  main_result++;
270  printf ("Huffman read error\n");
271  EXIT;
272  }
273 
274 }
275 
276 
277 /*
278  * Decode one MCU
279  */
280 void
281 DecodeHuffMCU (int *out_buf, int num_cmp)
282 {
283  int s, diff, tbl_no, *mptr, k, n, r;
284 
285  /*
286  * Decode DC
287  */
288  tbl_no = p_jinfo_comps_info_dc_tbl_no[num_cmp];
290  p_jinfo_dc_dhuff_tbl_ml[tbl_no],
291  &p_jinfo_dc_dhuff_tbl_maxcode[tbl_no][0],
292  &p_jinfo_dc_dhuff_tbl_mincode[tbl_no][0],
293  &p_jinfo_dc_dhuff_tbl_valptr[tbl_no][0]);
294 
295  if (s)
296  {
297  diff = buf_getv (s);
298  s--;
299  if ((diff & bit_set_mask[s]) == 0)
300  {
301  diff |= extend_mask[s];
302  diff++;
303  }
304 
305  diff += *out_buf; /* Change the last DC */
306  *out_buf = diff;
307  }
308 
309  /*
310  * Decode AC
311  */
312  /* Set all values to zero */
313  for (mptr = out_buf + 1; mptr < out_buf + DCTSIZE2; mptr++)
314  {
315  *mptr = 0;
316  }
317 
318  for (k = 1; k < DCTSIZE2;)
319  { /* JPEG Mistake */
321  p_jinfo_ac_dhuff_tbl_ml[tbl_no],
322  &p_jinfo_ac_dhuff_tbl_maxcode[tbl_no][0],
323  &p_jinfo_ac_dhuff_tbl_mincode[tbl_no][0],
324  &p_jinfo_ac_dhuff_tbl_valptr[tbl_no][0]);
325 
326  s = r & 0xf; /* Find significant bits */
327  n = (r >> 4) & 0xf; /* n = run-length */
328 
329  if (s)
330  {
331  if ((k += n) >= DCTSIZE2) /* JPEG Mistake */
332  break;
333  out_buf[k] = buf_getv (s); /* Get s bits */
334  s--; /* Align s */
335  if ((out_buf[k] & bit_set_mask[s]) == 0)
336  { /* Also (1 << s) */
337  out_buf[k] |= extend_mask[s]; /* Also (-1 << s) + 1 */
338  out_buf[k]++; /* Increment 2's c */
339  }
340  k++; /* Goto next element */
341  }
342  else if (n == 15) /* Zero run length code extnd */
343  k += 16;
344  else
345  {
346  break;
347  }
348  }
349 }
int p_jinfo_dc_dhuff_tbl_mincode[NUM_HUFF_TBLS][36]
Definition: decode.h:94
int p_jinfo_dc_dhuff_tbl_maxcode[NUM_HUFF_TBLS][36]
Definition: decode.h:93
#define EXIT
Definition: global.h:46
#define MARKER_MARKER
Definition: decode.h:64
int buf_getb()
Definition: huffman.c:116
int DecodeHuffman(int *Xhuff_huffval, int Dhuff_ml, int *Dhuff_maxcode, int *Dhuff_mincode, int *Dhuff_valptr)
Definition: huffman.c:251
int huff_make_dhuff_tb(int *p_xhtbl_bits, int p_dhtbl_ml, int *p_dhtbl_maxcode, int *p_dhtbl_mincode, int *p_dhtbl_valptr)
Definition: huffman.c:179
static const int extend_mask[20]
Definition: huffman.c:54
int main_result
Definition: mips.c:38
const int bit_set_mask[32]
Definition: huffman.c:63
static unsigned int current_read_byte
Definition: huffman.c:85
int p_jinfo_ac_dhuff_tbl_maxcode[NUM_HUFF_TBLS][36]
Definition: decode.h:98
static int pgetc()
Definition: huffman.c:93
static const uint32_t k[]
Definition: sha-256.c:22
int p_jinfo_ac_dhuff_tbl_valptr[NUM_HUFF_TBLS][36]
Definition: decode.h:100
unsigned char * CurHuffReadBuf
Definition: huffman.h:38
int buf_getv(int n)
Definition: huffman.c:137
void DecodeHuffMCU(int *out_buf, int num_cmp)
Definition: huffman.c:281
int p_jinfo_dc_dhuff_tbl_ml[NUM_HUFF_TBLS]
Definition: decode.h:92
int p_jinfo_ac_dhuff_tbl_mincode[NUM_HUFF_TBLS][36]
Definition: decode.h:99
int p_jinfo_ac_xhuff_tbl_huffval[NUM_HUFF_TBLS][257]
Definition: decode.h:90
const int lmask[32]
Definition: huffman.c:74
#define DCTSIZE2
Definition: decode.h:49
char p_jinfo_comps_info_dc_tbl_no[NUM_COMPONENT]
Definition: decode.h:81
int p_jinfo_ac_dhuff_tbl_ml[NUM_HUFF_TBLS]
Definition: decode.h:97
int p_jinfo_dc_xhuff_tbl_huffval[NUM_HUFF_TBLS][257]
Definition: decode.h:87
static int read_position
Definition: huffman.c:86
int p_jinfo_dc_dhuff_tbl_valptr[NUM_HUFF_TBLS][36]
Definition: decode.h:95

Generated on Mon Feb 12 2024 13:02:49 for PandA-2024.02 by doxygen 1.8.13