]>
Commit | Line | Data |
---|---|---|
964dd0bc JW |
1 | /* JOrbis |
2 | * Copyright (C) 2000 ymnk, JCraft,Inc. | |
3 | * | |
4 | * Written by: 2000 ymnk<ymnk@jcraft.com> | |
5 | * | |
6 | * Many thanks to | |
7 | * Monty <monty@xiph.org> and | |
8 | * The XIPHOPHORUS Company http://www.xiph.org/ . | |
9 | * JOrbis has been based on their awesome works, Vorbis codec. | |
10 | * | |
11 | * This program is free software; you can redistribute it and/or | |
12 | * modify it under the terms of the GNU Library General Public License | |
13 | * as published by the Free Software Foundation; either version 2 of | |
14 | * the License, or (at your option) any later version. | |
15 | ||
16 | * This program is distributed in the hope that it will be useful, | |
17 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
18 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
19 | * GNU Library General Public License for more details. | |
20 | * | |
21 | * You should have received a copy of the GNU Library General Public | |
22 | * License along with this program; if not, write to the Free Software | |
23 | * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. | |
24 | */ | |
25 | ||
26 | package com.jcraft.jorbis; | |
27 | ||
28 | import com.jcraft.jogg.*; | |
29 | ||
30 | class StaticCodeBook{ | |
31 | int dim; // codebook dimensions (elements per vector) | |
32 | int entries; // codebook entries | |
33 | int[] lengthlist; // codeword lengths in bits | |
34 | ||
35 | // mapping | |
36 | int maptype; // 0=none | |
37 | // 1=implicitly populated values from map column | |
38 | // 2=listed arbitrary values | |
39 | ||
40 | // The below does a linear, single monotonic sequence mapping. | |
41 | int q_min; // packed 32 bit float; quant value 0 maps to minval | |
42 | int q_delta; // packed 32 bit float; val 1 - val 0 == delta | |
43 | int q_quant; // bits: 0 < quant <= 16 | |
44 | int q_sequencep; // bitflag | |
45 | ||
46 | // additional information for log (dB) mapping; the linear mapping | |
47 | // is assumed to actually be values in dB. encodebias is used to | |
48 | // assign an error weight to 0 dB. We have two additional flags: | |
49 | // zeroflag indicates if entry zero is to represent -Inf dB; negflag | |
50 | // indicates if we're to represent negative linear values in a | |
51 | // mirror of the positive mapping. | |
52 | ||
53 | int[] quantlist; // map == 1: (int)(entries/dim) element column map | |
54 | // map == 2: list of dim*entries quantized entry vals | |
55 | ||
56 | // encode helpers | |
57 | EncodeAuxNearestMatch nearest_tree; | |
58 | EncodeAuxThreshMatch thresh_tree; | |
59 | ||
60 | StaticCodeBook(){} | |
61 | StaticCodeBook(int dim, int entries, int[] lengthlist, | |
62 | int maptype, int q_min, int q_delta, | |
63 | int q_quant, int q_sequencep, int[] quantlist, | |
64 | //EncodeAuxNearestmatch nearest_tree, | |
65 | Object nearest_tree, | |
66 | // EncodeAuxThreshmatch thresh_tree, | |
67 | Object thresh_tree | |
68 | ){ | |
69 | this(); | |
70 | this.dim=dim; this.entries=entries; this.lengthlist=lengthlist; | |
71 | this.maptype=maptype; this.q_min=q_min; this.q_delta=q_delta; | |
72 | this.q_quant=q_quant; this.q_sequencep=q_sequencep; | |
73 | this.quantlist=quantlist; | |
74 | } | |
75 | ||
76 | int pack(Buffer opb){ | |
77 | int i; | |
78 | boolean ordered=false; | |
79 | ||
80 | opb.write(0x564342,24); | |
81 | opb.write(dim, 16); | |
82 | opb.write(entries, 24); | |
83 | ||
84 | // pack the codewords. There are two packings; length ordered and | |
85 | // length random. Decide between the two now. | |
86 | ||
87 | for(i=1;i<entries;i++){ | |
88 | if(lengthlist[i]<lengthlist[i-1])break; | |
89 | } | |
90 | if(i==entries)ordered=true; | |
91 | ||
92 | if(ordered){ | |
93 | // length ordered. We only need to say how many codewords of | |
94 | // each length. The actual codewords are generated | |
95 | // deterministically | |
96 | ||
97 | int count=0; | |
98 | opb.write(1,1); // ordered | |
99 | opb.write(lengthlist[0]-1,5); // 1 to 32 | |
100 | ||
101 | for(i=1;i<entries;i++){ | |
102 | int _this=lengthlist[i]; | |
103 | int _last=lengthlist[i-1]; | |
104 | if(_this>_last){ | |
105 | for(int j=_last;j<_this;j++){ | |
106 | opb.write(i-count,ilog(entries-count)); | |
107 | count=i; | |
108 | } | |
109 | } | |
110 | } | |
111 | opb.write(i-count,ilog(entries-count)); | |
112 | } | |
113 | else{ | |
114 | // length random. Again, we don't code the codeword itself, just | |
115 | // the length. This time, though, we have to encode each length | |
116 | opb.write(0,1); // unordered | |
117 | ||
118 | // algortihmic mapping has use for 'unused entries', which we tag | |
119 | // here. The algorithmic mapping happens as usual, but the unused | |
120 | // entry has no codeword. | |
121 | for(i=0;i<entries;i++){ | |
122 | if(lengthlist[i]==0)break; | |
123 | } | |
124 | ||
125 | if(i==entries){ | |
126 | opb.write(0,1); // no unused entries | |
127 | for(i=0;i<entries;i++){ | |
128 | opb.write(lengthlist[i]-1,5); | |
129 | } | |
130 | } | |
131 | else{ | |
132 | opb.write(1,1); // we have unused entries; thus we tag | |
133 | for(i=0;i<entries;i++){ | |
134 | if(lengthlist[i]==0){ | |
135 | opb.write(0,1); | |
136 | } | |
137 | else{ | |
138 | opb.write(1,1); | |
139 | opb.write(lengthlist[i]-1,5); | |
140 | } | |
141 | } | |
142 | } | |
143 | } | |
144 | ||
145 | // is the entry number the desired return value, or do we have a | |
146 | // mapping? If we have a mapping, what type? | |
147 | opb.write(maptype,4); | |
148 | switch(maptype){ | |
149 | case 0: | |
150 | // no mapping | |
151 | break; | |
152 | case 1: | |
153 | case 2: | |
154 | // implicitly populated value mapping | |
155 | // explicitly populated value mapping | |
156 | if(quantlist==null){ | |
157 | // no quantlist? error | |
158 | return(-1); | |
159 | } | |
160 | ||
161 | // values that define the dequantization | |
162 | opb.write(q_min,32); | |
163 | opb.write(q_delta,32); | |
164 | opb.write(q_quant-1,4); | |
165 | opb.write(q_sequencep,1); | |
166 | ||
167 | { | |
168 | int quantvals=0; | |
169 | switch(maptype){ | |
170 | case 1: | |
171 | // a single column of (c->entries/c->dim) quantized values for | |
172 | // building a full value list algorithmically (square lattice) | |
173 | quantvals=maptype1_quantvals(); | |
174 | break; | |
175 | case 2: | |
176 | // every value (c->entries*c->dim total) specified explicitly | |
177 | quantvals=entries*dim; | |
178 | break; | |
179 | } | |
180 | ||
181 | // quantized values | |
182 | for(i=0;i<quantvals;i++){ | |
183 | opb.write(Math.abs(quantlist[i]),q_quant); | |
184 | } | |
185 | } | |
186 | break; | |
187 | default: | |
188 | // error case; we don't have any other map types now | |
189 | return(-1); | |
190 | } | |
191 | return(0); | |
192 | } | |
193 | /* | |
194 | */ | |
195 | ||
196 | // unpacks a codebook from the packet buffer into the codebook struct, | |
197 | // readies the codebook auxiliary structures for decode | |
198 | int unpack(Buffer opb){ | |
199 | int i; | |
200 | //memset(s,0,sizeof(static_codebook)); | |
201 | ||
202 | // make sure alignment is correct | |
203 | if(opb.read(24)!=0x564342){ | |
204 | // goto _eofout; | |
205 | clear(); | |
206 | return(-1); | |
207 | } | |
208 | ||
209 | // first the basic parameters | |
210 | dim=opb.read(16); | |
211 | entries=opb.read(24); | |
212 | if(entries==-1){ | |
213 | // goto _eofout; | |
214 | clear(); | |
215 | return(-1); | |
216 | } | |
217 | ||
218 | // codeword ordering.... length ordered or unordered? | |
219 | switch(opb.read(1)){ | |
220 | case 0: | |
221 | // unordered | |
222 | lengthlist=new int[entries]; | |
223 | ||
224 | // allocated but unused entries? | |
225 | if(opb.read(1)!=0){ | |
226 | // yes, unused entries | |
227 | ||
228 | for(i=0;i<entries;i++){ | |
229 | if(opb.read(1)!=0){ | |
230 | int num=opb.read(5); | |
231 | if(num==-1){ | |
232 | // goto _eofout; | |
233 | clear(); | |
234 | return(-1); | |
235 | } | |
236 | lengthlist[i]=num+1; | |
237 | } | |
238 | else{ | |
239 | lengthlist[i]=0; | |
240 | } | |
241 | } | |
242 | } | |
243 | else{ | |
244 | // all entries used; no tagging | |
245 | for(i=0;i<entries;i++){ | |
246 | int num=opb.read(5); | |
247 | if(num==-1){ | |
248 | // goto _eofout; | |
249 | clear(); | |
250 | return(-1); | |
251 | } | |
252 | lengthlist[i]=num+1; | |
253 | } | |
254 | } | |
255 | break; | |
256 | case 1: | |
257 | // ordered | |
258 | { | |
259 | int length=opb.read(5)+1; | |
260 | lengthlist=new int[entries]; | |
261 | ||
262 | for(i=0;i<entries;){ | |
263 | int num=opb.read(ilog(entries-i)); | |
264 | if(num==-1){ | |
265 | // goto _eofout; | |
266 | clear(); | |
267 | return(-1); | |
268 | } | |
269 | for(int j=0;j<num;j++,i++){ | |
270 | lengthlist[i]=length; | |
271 | } | |
272 | length++; | |
273 | } | |
274 | } | |
275 | break; | |
276 | default: | |
277 | // EOF | |
278 | return(-1); | |
279 | } | |
280 | ||
281 | // Do we have a mapping to unpack? | |
282 | switch((maptype=opb.read(4))){ | |
283 | case 0: | |
284 | // no mapping | |
285 | break; | |
286 | case 1: | |
287 | case 2: | |
288 | // implicitly populated value mapping | |
289 | // explicitly populated value mapping | |
290 | q_min=opb.read(32); | |
291 | q_delta=opb.read(32); | |
292 | q_quant=opb.read(4)+1; | |
293 | q_sequencep=opb.read(1); | |
294 | ||
295 | { | |
296 | int quantvals=0; | |
297 | switch(maptype){ | |
298 | case 1: | |
299 | quantvals=maptype1_quantvals(); | |
300 | break; | |
301 | case 2: | |
302 | quantvals=entries*dim; | |
303 | break; | |
304 | } | |
305 | ||
306 | // quantized values | |
307 | quantlist=new int[quantvals]; | |
308 | for(i=0;i<quantvals;i++){ | |
309 | quantlist[i]=opb.read(q_quant); | |
310 | } | |
311 | if(quantlist[quantvals-1]==-1){ | |
312 | // goto _eofout; | |
313 | clear(); | |
314 | return(-1); | |
315 | } | |
316 | } | |
317 | break; | |
318 | default: | |
319 | // goto _eofout; | |
320 | clear(); | |
321 | return(-1); | |
322 | } | |
323 | // all set | |
324 | return(0); | |
325 | // _errout: | |
326 | // _eofout: | |
327 | // vorbis_staticbook_clear(s); | |
328 | // return(-1); | |
329 | } | |
330 | ||
331 | // there might be a straightforward one-line way to do the below | |
332 | // that's portable and totally safe against roundoff, but I haven't | |
333 | // thought of it. Therefore, we opt on the side of caution | |
334 | private int maptype1_quantvals(){ | |
335 | int vals=(int)(Math.floor(Math.pow(entries,1./dim))); | |
336 | ||
337 | // the above *should* be reliable, but we'll not assume that FP is | |
338 | // ever reliable when bitstream sync is at stake; verify via integer | |
339 | // means that vals really is the greatest value of dim for which | |
340 | // vals^b->bim <= b->entries | |
341 | // treat the above as an initial guess | |
342 | while(true){ | |
343 | int acc=1; | |
344 | int acc1=1; | |
345 | for(int i=0;i<dim;i++){ | |
346 | acc*=vals; | |
347 | acc1*=vals+1; | |
348 | } | |
349 | if(acc<=entries && acc1>entries){ return(vals); } | |
350 | else{ | |
351 | if(acc>entries){ vals--; } | |
352 | else{ vals++; } | |
353 | } | |
354 | } | |
355 | } | |
356 | ||
357 | void clear(){ | |
358 | // if(quantlist!=null)free(b->quantlist); | |
359 | // if(lengthlist!=null)free(b->lengthlist); | |
360 | // if(nearest_tree!=null){ | |
361 | // free(b->nearest_tree->ptr0); | |
362 | // free(b->nearest_tree->ptr1); | |
363 | // free(b->nearest_tree->p); | |
364 | // free(b->nearest_tree->q); | |
365 | // memset(b->nearest_tree,0,sizeof(encode_aux_nearestmatch)); | |
366 | // free(b->nearest_tree); | |
367 | // } | |
368 | // if(thresh_tree!=null){ | |
369 | // free(b->thresh_tree->quantthresh); | |
370 | // free(b->thresh_tree->quantmap); | |
371 | // memset(b->thresh_tree,0,sizeof(encode_aux_threshmatch)); | |
372 | // free(b->thresh_tree); | |
373 | // } | |
374 | // memset(b,0,sizeof(static_codebook)); | |
375 | } | |
376 | ||
377 | // unpack the quantized list of values for encode/decode | |
378 | // we need to deal with two map types: in map type 1, the values are | |
379 | // generated algorithmically (each column of the vector counts through | |
380 | // the values in the quant vector). in map type 2, all the values came | |
381 | // in in an explicit list. Both value lists must be unpacked | |
382 | float[] unquantize(){ | |
383 | ||
384 | if(maptype==1 || maptype==2){ | |
385 | int quantvals; | |
386 | float mindel=float32_unpack(q_min); | |
387 | float delta=float32_unpack(q_delta); | |
388 | float[] r=new float[entries*dim]; | |
389 | ||
390 | //System.err.println("q_min="+q_min+", mindel="+mindel); | |
391 | ||
392 | // maptype 1 and 2 both use a quantized value vector, but | |
393 | // different sizes | |
394 | switch(maptype){ | |
395 | case 1: | |
396 | // most of the time, entries%dimensions == 0, but we need to be | |
397 | // well defined. We define that the possible vales at each | |
398 | // scalar is values == entries/dim. If entries%dim != 0, we'll | |
399 | // have 'too few' values (values*dim<entries), which means that | |
400 | // we'll have 'left over' entries; left over entries use zeroed | |
401 | // values (and are wasted). So don't generate codebooks like that | |
402 | quantvals=maptype1_quantvals(); | |
403 | for(int j=0;j<entries;j++){ | |
404 | float last=0.f; | |
405 | int indexdiv=1; | |
406 | for(int k=0;k<dim;k++){ | |
407 | int index=(j/indexdiv)%quantvals; | |
408 | float val=quantlist[index]; | |
409 | val=Math.abs(val)*delta+mindel+last; | |
410 | if(q_sequencep!=0)last=val; | |
411 | r[j*dim+k]=val; | |
412 | indexdiv*=quantvals; | |
413 | } | |
414 | } | |
415 | break; | |
416 | case 2: | |
417 | for(int j=0;j<entries;j++){ | |
418 | float last=0.f; | |
419 | for(int k=0;k<dim;k++){ | |
420 | float val=quantlist[j*dim+k]; | |
421 | //if((j*dim+k)==0){System.err.println(" | 0 -> "+val+" | ");} | |
422 | val=Math.abs(val)*delta+mindel+last; | |
423 | if(q_sequencep!=0)last=val; | |
424 | r[j*dim+k]=val; | |
425 | //if((j*dim+k)==0){System.err.println(" $ r[0] -> "+r[0]+" | ");} | |
426 | } | |
427 | } | |
428 | //System.err.println("\nr[0]="+r[0]); | |
429 | } | |
430 | return(r); | |
431 | } | |
432 | return(null); | |
433 | } | |
434 | ||
435 | private static int ilog(int v){ | |
436 | int ret=0; | |
437 | while(v!=0){ | |
438 | ret++; | |
439 | v>>>=1; | |
440 | } | |
441 | return(ret); | |
442 | } | |
443 | ||
444 | // 32 bit float (not IEEE; nonnormalized mantissa + | |
445 | // biased exponent) : neeeeeee eeemmmmm mmmmmmmm mmmmmmmm | |
446 | // Why not IEEE? It's just not that important here. | |
447 | ||
448 | static final int VQ_FEXP=10; | |
449 | static final int VQ_FMAN=21; | |
450 | static final int VQ_FEXP_BIAS=768; // bias toward values smaller than 1. | |
451 | ||
452 | // doesn't currently guard under/overflow | |
453 | static long float32_pack(float val){ | |
454 | int sign=0; | |
455 | int exp; | |
456 | int mant; | |
457 | if(val<0){ | |
458 | sign=0x80000000; | |
459 | val= -val; | |
460 | } | |
461 | exp=(int)Math.floor(Math.log(val)/Math.log(2)); | |
462 | mant=(int)Math.rint(Math.pow(val,(VQ_FMAN-1)-exp)); | |
463 | exp=(exp+VQ_FEXP_BIAS)<<VQ_FMAN; | |
464 | return(sign|exp|mant); | |
465 | } | |
466 | ||
467 | static float float32_unpack(int val){ | |
468 | float mant=val&0x1fffff; | |
469 | float sign=val&0x80000000; | |
470 | float exp =(val&0x7fe00000)>>>VQ_FMAN; | |
471 | //System.err.println("mant="+mant+", sign="+sign+", exp="+exp); | |
472 | //if(sign!=0.0)mant= -mant; | |
473 | if((val&0x80000000)!=0)mant= -mant; | |
474 | //System.err.println("mant="+mant); | |
475 | return(ldexp(mant,((int)exp)-(VQ_FMAN-1)-VQ_FEXP_BIAS)); | |
476 | } | |
477 | ||
478 | static float ldexp(float foo, int e){ | |
479 | return (float)(foo*Math.pow(2, e)); | |
480 | } | |
481 | ||
482 | /* | |
483 | // TEST | |
484 | // Unit tests of the dequantizer; this stuff will be OK | |
485 | // cross-platform, I simply want to be sure that special mapping cases | |
486 | // actually work properly; a bug could go unnoticed for a while | |
487 | ||
488 | // cases: | |
489 | // | |
490 | // no mapping | |
491 | // full, explicit mapping | |
492 | // algorithmic mapping | |
493 | // | |
494 | // nonsequential | |
495 | // sequential | |
496 | ||
497 | static int[] full_quantlist1={0,1,2,3, 4,5,6,7, 8,3,6,1}; | |
498 | static int[] partial_quantlist1={0,7,2}; | |
499 | ||
500 | // no mapping | |
501 | static StaticCodeBook test1=new StaticCodeBook(4,16,null, | |
502 | 0,0,0,0,0, | |
503 | null,null,null); | |
504 | static float[] test1_result=null; | |
505 | ||
506 | // linear, full mapping, nonsequential | |
507 | static StaticCodeBook test2=new StaticCodeBook(4,3,null, | |
508 | 2,-533200896,1611661312,4,0, | |
509 | full_quantlist1, null, null); | |
510 | static float[] test2_result={-3,-2,-1,0, 1,2,3,4, 5,0,3,-2}; | |
511 | ||
512 | // linear, full mapping, sequential | |
513 | static StaticCodeBook test3=new StaticCodeBook(4,3,null, | |
514 | 2, -533200896,1611661312,4,1, | |
515 | full_quantlist1,null, null); | |
516 | static float[] test3_result={-3,-5,-6,-6, 1,3,6,10, 5,5,8,6}; | |
517 | ||
518 | // linear, algorithmic mapping, nonsequential | |
519 | static StaticCodeBook test4=new StaticCodeBook(3,27,null, | |
520 | 1,-533200896,1611661312,4,0, | |
521 | partial_quantlist1,null,null); | |
522 | static float[] test4_result={-3,-3,-3, 4,-3,-3, -1,-3,-3, | |
523 | -3, 4,-3, 4, 4,-3, -1, 4,-3, | |
524 | -3,-1,-3, 4,-1,-3, -1,-1,-3, | |
525 | -3,-3, 4, 4,-3, 4, -1,-3, 4, | |
526 | -3, 4, 4, 4, 4, 4, -1, 4, 4, | |
527 | -3,-1, 4, 4,-1, 4, -1,-1, 4, | |
528 | -3,-3,-1, 4,-3,-1, -1,-3,-1, | |
529 | -3, 4,-1, 4, 4,-1, -1, 4,-1, | |
530 | -3,-1,-1, 4,-1,-1, -1,-1,-1}; | |
531 | ||
532 | // linear, algorithmic mapping, sequential | |
533 | static StaticCodeBook test5=new StaticCodeBook(3,27,null, | |
534 | 1,-533200896,1611661312,4,1, | |
535 | partial_quantlist1,null,null); | |
536 | static float[] test5_result={-3,-6,-9, 4, 1,-2, -1,-4,-7, | |
537 | -3, 1,-2, 4, 8, 5, -1, 3, 0, | |
538 | -3,-4,-7, 4, 3, 0, -1,-2,-5, | |
539 | -3,-6,-2, 4, 1, 5, -1,-4, 0, | |
540 | -3, 1, 5, 4, 8,12, -1, 3, 7, | |
541 | -3,-4, 0, 4, 3, 7, -1,-2, 2, | |
542 | -3,-6,-7, 4, 1, 0, -1,-4,-5, | |
543 | -3, 1, 0, 4, 8, 7, -1, 3, 2, | |
544 | -3,-4,-5, 4, 3, 2, -1,-2,-3}; | |
545 | ||
546 | void run_test(float[] comp){ | |
547 | float[] out=unquantize(); | |
548 | if(comp!=null){ | |
549 | if(out==null){ | |
550 | System.err.println("_book_unquantize incorrectly returned NULL"); | |
551 | System.exit(1); | |
552 | } | |
553 | for(int i=0;i<entries*dim;i++){ | |
554 | if(Math.abs(out[i]-comp[i])>.0001){ | |
555 | System.err.println("disagreement in unquantized and reference data:\nposition "+i+": "+out[i]+" != "+comp[i]); | |
556 | System.exit(1); | |
557 | } | |
558 | } | |
559 | } | |
560 | else{ | |
561 | if(out!=null){ | |
562 | System.err.println("_book_unquantize returned a value array:\n correct result should have been NULL"); | |
563 | System.exit(1); | |
564 | } | |
565 | } | |
566 | } | |
567 | ||
568 | public static void main(String[] arg){ | |
569 | // run the nine dequant tests, and compare to the hand-rolled results | |
570 | System.err.print("Dequant test 1... "); | |
571 | test1.run_test(test1_result); | |
572 | System.err.print("OK\nDequant test 2... "); | |
573 | test2.run_test(test2_result); | |
574 | System.err.print("OK\nDequant test 3... "); | |
575 | test3.run_test(test3_result); | |
576 | System.err.print("OK\nDequant test 4... "); | |
577 | test4.run_test(test4_result); | |
578 | System.err.print("OK\nDequant test 5... "); | |
579 | test5.run_test(test5_result); | |
580 | System.err.print("OK\n\n"); | |
581 | } | |
582 | */ | |
583 | } | |
584 | ||
585 | ||
586 | ||
587 | ||
588 |