Gloria Wang | 37fe158 | 2010-03-12 14:53:20 -0800 | [diff] [blame] | 1 | /************************************************************************ |
Gloria Wang | 2da723a | 2010-03-18 15:56:16 -0700 | [diff] [blame] | 2 | * Copyright (C) 2002-2009, Xiph.org Foundation |
| 3 | * Copyright (C) 2010, Robin Watts for Pinknoise Productions Ltd |
Gloria Wang | 37fe158 | 2010-03-12 14:53:20 -0800 | [diff] [blame] | 4 | * All rights reserved. |
| 5 | * |
| 6 | * Redistribution and use in source and binary forms, with or without |
Gloria Wang | 2da723a | 2010-03-18 15:56:16 -0700 | [diff] [blame] | 7 | * modification, are permitted provided that the following conditions |
| 8 | * are met: |
Gloria Wang | 37fe158 | 2010-03-12 14:53:20 -0800 | [diff] [blame] | 9 | * |
| 10 | * * Redistributions of source code must retain the above copyright |
| 11 | * notice, this list of conditions and the following disclaimer. |
| 12 | * * Redistributions in binary form must reproduce the above |
| 13 | * copyright notice, this list of conditions and the following disclaimer |
| 14 | * in the documentation and/or other materials provided with the |
| 15 | * distribution. |
Gloria Wang | 2da723a | 2010-03-18 15:56:16 -0700 | [diff] [blame] | 16 | * * Neither the names of the Xiph.org Foundation nor Pinknoise |
| 17 | * Productions Ltd nor the names of its contributors may be used to |
| 18 | * endorse or promote products derived from this software without |
| 19 | * specific prior written permission. |
Gloria Wang | 37fe158 | 2010-03-12 14:53:20 -0800 | [diff] [blame] | 20 | * |
| 21 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
| 22 | * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
| 23 | * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
| 24 | * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
| 25 | * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
| 26 | * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT |
| 27 | * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
| 28 | * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
| 29 | * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| 30 | * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
| 31 | * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| 32 | ************************************************************************ |
Gloria Wang | 7913073 | 2010-02-08 14:41:04 -0800 | [diff] [blame] | 33 | |
| 34 | function: floor backend 1 implementation |
| 35 | |
Gloria Wang | 37fe158 | 2010-03-12 14:53:20 -0800 | [diff] [blame] | 36 | ************************************************************************/ |
Gloria Wang | 7913073 | 2010-02-08 14:41:04 -0800 | [diff] [blame] | 37 | |
| 38 | #include <stdlib.h> |
| 39 | #include <string.h> |
| 40 | #include <math.h> |
| 41 | #include "ogg.h" |
| 42 | #include "ivorbiscodec.h" |
| 43 | #include "codec_internal.h" |
| 44 | #include "codebook.h" |
| 45 | #include "misc.h" |
| 46 | |
| 47 | extern const ogg_int32_t FLOOR_fromdB_LOOKUP[]; |
| 48 | #define floor1_rangedB 140 /* floor 1 fixed at -140dB to 0dB range */ |
| 49 | #define VIF_POSIT 63 |
| 50 | |
| 51 | /***********************************************/ |
| 52 | |
| 53 | void floor1_free_info(vorbis_info_floor *i){ |
| 54 | vorbis_info_floor1 *info=(vorbis_info_floor1 *)i; |
| 55 | if(info){ |
Andreas Huber | 1a7ca64 | 2010-05-07 10:37:02 -0700 | [diff] [blame] | 56 | if(info->klass)_ogg_free(info->klass); |
Gloria Wang | 7913073 | 2010-02-08 14:41:04 -0800 | [diff] [blame] | 57 | if(info->partitionclass)_ogg_free(info->partitionclass); |
| 58 | if(info->postlist)_ogg_free(info->postlist); |
| 59 | if(info->forward_index)_ogg_free(info->forward_index); |
| 60 | if(info->hineighbor)_ogg_free(info->hineighbor); |
| 61 | if(info->loneighbor)_ogg_free(info->loneighbor); |
| 62 | memset(info,0,sizeof(*info)); |
| 63 | _ogg_free(info); |
| 64 | } |
| 65 | } |
| 66 | |
| 67 | static int ilog(unsigned int v){ |
| 68 | int ret=0; |
| 69 | while(v){ |
| 70 | ret++; |
| 71 | v>>=1; |
| 72 | } |
| 73 | return(ret); |
| 74 | } |
| 75 | |
Glenn Kasten | 946e1bc | 2016-04-06 07:47:11 -0700 | [diff] [blame] | 76 | static void mergesort(ogg_uint8_t *index,ogg_uint16_t *vals,ogg_uint16_t n){ |
Gloria Wang | 7913073 | 2010-02-08 14:41:04 -0800 | [diff] [blame] | 77 | ogg_uint16_t i,j; |
Glenn Kasten | 946e1bc | 2016-04-06 07:47:11 -0700 | [diff] [blame] | 78 | ogg_uint8_t *temp,*A=index,*B=_ogg_malloc(n*sizeof(*B)); |
Gloria Wang | 7913073 | 2010-02-08 14:41:04 -0800 | [diff] [blame] | 79 | |
| 80 | for(i=1;i<n;i<<=1){ |
| 81 | for(j=0;j+i<n;){ |
| 82 | int k1=j; |
| 83 | int mid=j+i; |
| 84 | int k2=mid; |
| 85 | int end=(j+i*2<n?j+i*2:n); |
| 86 | while(k1<mid && k2<end){ |
| 87 | if(vals[A[k1]]<vals[A[k2]]) |
| 88 | B[j++]=A[k1++]; |
| 89 | else |
| 90 | B[j++]=A[k2++]; |
| 91 | } |
| 92 | while(k1<mid) B[j++]=A[k1++]; |
| 93 | while(k2<end) B[j++]=A[k2++]; |
| 94 | } |
| 95 | for(;j<n;j++)B[j]=A[j]; |
| 96 | temp=A;A=B;B=temp; |
| 97 | } |
| 98 | |
| 99 | if(B==index){ |
| 100 | for(j=0;j<n;j++)B[j]=A[j]; |
| 101 | _ogg_free(A); |
| 102 | }else |
| 103 | _ogg_free(B); |
| 104 | } |
| 105 | |
| 106 | |
| 107 | vorbis_info_floor *floor1_info_unpack (vorbis_info *vi,oggpack_buffer *opb){ |
| 108 | codec_setup_info *ci=(codec_setup_info *)vi->codec_setup; |
| 109 | int j,k,count=0,maxclass=-1,rangebits; |
| 110 | |
| 111 | vorbis_info_floor1 *info=(vorbis_info_floor1 *)_ogg_calloc(1,sizeof(*info)); |
| 112 | /* read partitions */ |
| 113 | info->partitions=oggpack_read(opb,5); /* only 0 to 31 legal */ |
| 114 | info->partitionclass= |
Glenn Kasten | 946e1bc | 2016-04-06 07:47:11 -0700 | [diff] [blame] | 115 | (ogg_uint8_t *)_ogg_malloc(info->partitions*sizeof(*info->partitionclass)); |
Gloria Wang | 7913073 | 2010-02-08 14:41:04 -0800 | [diff] [blame] | 116 | for(j=0;j<info->partitions;j++){ |
| 117 | info->partitionclass[j]=(char)oggpack_read(opb,4); /* only 0 to 15 legal */ |
| 118 | if(maxclass<info->partitionclass[j])maxclass=info->partitionclass[j]; |
| 119 | } |
| 120 | |
| 121 | /* read partition classes */ |
Andreas Huber | 1a7ca64 | 2010-05-07 10:37:02 -0700 | [diff] [blame] | 122 | info->klass= |
| 123 | (floor1class *)_ogg_malloc((maxclass+1)*sizeof(*info->klass)); |
Gloria Wang | 7913073 | 2010-02-08 14:41:04 -0800 | [diff] [blame] | 124 | for(j=0;j<maxclass+1;j++){ |
Andreas Huber | 1a7ca64 | 2010-05-07 10:37:02 -0700 | [diff] [blame] | 125 | info->klass[j].class_dim=(char)oggpack_read(opb,3)+1; /* 1 to 8 */ |
| 126 | info->klass[j].class_subs=(char)oggpack_read(opb,2); /* 0,1,2,3 bits */ |
Gloria Wang | 7913073 | 2010-02-08 14:41:04 -0800 | [diff] [blame] | 127 | if(oggpack_eop(opb)<0) goto err_out; |
Andreas Huber | 1a7ca64 | 2010-05-07 10:37:02 -0700 | [diff] [blame] | 128 | if(info->klass[j].class_subs) |
| 129 | info->klass[j].class_book=(unsigned char)oggpack_read(opb,8); |
Gloria Wang | 7913073 | 2010-02-08 14:41:04 -0800 | [diff] [blame] | 130 | else |
Andreas Huber | 1a7ca64 | 2010-05-07 10:37:02 -0700 | [diff] [blame] | 131 | info->klass[j].class_book=0; |
| 132 | if(info->klass[j].class_book>=ci->books)goto err_out; |
| 133 | for(k=0;k<(1<<info->klass[j].class_subs);k++){ |
| 134 | info->klass[j].class_subbook[k]=(unsigned char)(oggpack_read(opb,8)-1); |
| 135 | if(info->klass[j].class_subbook[k]>=ci->books && |
| 136 | info->klass[j].class_subbook[k]!=0xff)goto err_out; |
Gloria Wang | 7913073 | 2010-02-08 14:41:04 -0800 | [diff] [blame] | 137 | } |
| 138 | } |
| 139 | |
| 140 | /* read the post list */ |
| 141 | info->mult=oggpack_read(opb,2)+1; /* only 1,2,3,4 legal now */ |
| 142 | rangebits=oggpack_read(opb,4); |
| 143 | |
| 144 | for(j=0,k=0;j<info->partitions;j++) |
Andreas Huber | 1a7ca64 | 2010-05-07 10:37:02 -0700 | [diff] [blame] | 145 | count+=info->klass[info->partitionclass[j]].class_dim; |
Gloria Wang | 7913073 | 2010-02-08 14:41:04 -0800 | [diff] [blame] | 146 | info->postlist= |
| 147 | (ogg_uint16_t *)_ogg_malloc((count+2)*sizeof(*info->postlist)); |
| 148 | info->forward_index= |
Glenn Kasten | 946e1bc | 2016-04-06 07:47:11 -0700 | [diff] [blame] | 149 | (ogg_uint8_t *)_ogg_malloc((count+2)*sizeof(*info->forward_index)); |
Gloria Wang | 7913073 | 2010-02-08 14:41:04 -0800 | [diff] [blame] | 150 | info->loneighbor= |
Glenn Kasten | 946e1bc | 2016-04-06 07:47:11 -0700 | [diff] [blame] | 151 | (ogg_uint8_t *)_ogg_malloc(count*sizeof(*info->loneighbor)); |
Gloria Wang | 7913073 | 2010-02-08 14:41:04 -0800 | [diff] [blame] | 152 | info->hineighbor= |
Glenn Kasten | 946e1bc | 2016-04-06 07:47:11 -0700 | [diff] [blame] | 153 | (ogg_uint8_t *)_ogg_malloc(count*sizeof(*info->hineighbor)); |
Gloria Wang | 7913073 | 2010-02-08 14:41:04 -0800 | [diff] [blame] | 154 | |
| 155 | count=0; |
| 156 | for(j=0,k=0;j<info->partitions;j++){ |
Andreas Huber | 1a7ca64 | 2010-05-07 10:37:02 -0700 | [diff] [blame] | 157 | count+=info->klass[info->partitionclass[j]].class_dim; |
Gloria Wang | 7913073 | 2010-02-08 14:41:04 -0800 | [diff] [blame] | 158 | for(;k<count;k++){ |
| 159 | int t=info->postlist[k+2]=(ogg_uint16_t)oggpack_read(opb,rangebits); |
| 160 | if(t>=(1<<rangebits))goto err_out; |
| 161 | } |
| 162 | } |
| 163 | if(oggpack_eop(opb))goto err_out; |
| 164 | info->postlist[0]=0; |
| 165 | info->postlist[1]=1<<rangebits; |
| 166 | info->posts=count+2; |
| 167 | |
| 168 | /* also store a sorted position index */ |
| 169 | for(j=0;j<info->posts;j++)info->forward_index[j]=j; |
| 170 | mergesort(info->forward_index,info->postlist,info->posts); |
| 171 | |
| 172 | /* discover our neighbors for decode where we don't use fit flags |
| 173 | (that would push the neighbors outward) */ |
| 174 | for(j=0;j<info->posts-2;j++){ |
| 175 | int lo=0; |
| 176 | int hi=1; |
| 177 | int lx=0; |
| 178 | int hx=info->postlist[1]; |
| 179 | int currentx=info->postlist[j+2]; |
| 180 | for(k=0;k<j+2;k++){ |
| 181 | int x=info->postlist[k]; |
| 182 | if(x>lx && x<currentx){ |
| 183 | lo=k; |
| 184 | lx=x; |
| 185 | } |
| 186 | if(x<hx && x>currentx){ |
| 187 | hi=k; |
| 188 | hx=x; |
| 189 | } |
| 190 | } |
| 191 | info->loneighbor[j]=lo; |
| 192 | info->hineighbor[j]=hi; |
| 193 | } |
| 194 | |
| 195 | return(info); |
| 196 | |
| 197 | err_out: |
| 198 | floor1_free_info(info); |
| 199 | return(NULL); |
| 200 | } |
| 201 | |
| 202 | #ifdef ONLY_C |
| 203 | static |
| 204 | #endif |
| 205 | int render_point(int x0,int x1,int y0,int y1,int x){ |
| 206 | y0&=0x7fff; /* mask off flag */ |
| 207 | y1&=0x7fff; |
| 208 | |
| 209 | { |
| 210 | int dy=y1-y0; |
| 211 | int adx=x1-x0; |
| 212 | int ady=abs(dy); |
| 213 | int err=ady*(x-x0); |
| 214 | |
| 215 | int off=err/adx; |
| 216 | if(dy<0)return(y0-off); |
| 217 | return(y0+off); |
| 218 | } |
| 219 | } |
| 220 | |
| 221 | #ifndef ONLY_C |
| 222 | void render_lineARM(int n, ogg_int32_t *d,const ogg_int32_t *floor, int base, int err, int adx, int ady); |
| 223 | #endif |
| 224 | |
| 225 | static void render_line(int n,int x0,int x1,int y0,int y1,ogg_int32_t *d){ |
| 226 | int dy; |
| 227 | int adx; |
| 228 | int ady; |
| 229 | int base; |
| 230 | int err; |
| 231 | const ogg_int32_t *floor; |
| 232 | |
| 233 | if(n>x1)n=x1; |
| 234 | n -= x0; |
Marco Nelissen | c7fdab4 | 2015-05-12 13:04:25 -0700 | [diff] [blame] | 235 | if (n <= 0 || y0 < 0 || y0 > 255 || y1 < 0 || y1 > 255) { |
Gloria Wang | 7913073 | 2010-02-08 14:41:04 -0800 | [diff] [blame] | 236 | return; |
Marco Nelissen | c7fdab4 | 2015-05-12 13:04:25 -0700 | [diff] [blame] | 237 | } |
Gloria Wang | 7913073 | 2010-02-08 14:41:04 -0800 | [diff] [blame] | 238 | dy=y1-y0; |
| 239 | adx=x1-x0; |
| 240 | ady=abs(dy); |
| 241 | base=dy/adx; |
| 242 | err=adx-1; |
| 243 | floor=&FLOOR_fromdB_LOOKUP[y0]; |
| 244 | d += x0; |
| 245 | ady-=abs(base*adx); |
| 246 | |
| 247 | /* We should add base each time, and then: |
| 248 | * if dy >=0 we occasionally add 1 |
| 249 | * else occasionally subtract 1. |
| 250 | * As an optimisation we say that if dy <0 we make base 1 smaller. |
| 251 | * Then we need to add 1 occassionally, rather than subtract 1 - but we |
| 252 | * need to add 1 in all the cases when we wouldn't have done so before. |
| 253 | * Previously we'd have added 1 (100*ady/adx)% of the time. Now we want |
| 254 | * to do so (100*(adx-ady)/adx)% of the time. |
| 255 | */ |
| 256 | if (dy < 0){ |
| 257 | base--; |
| 258 | ady = adx-ady; |
| 259 | err = 0; |
| 260 | } |
| 261 | |
| 262 | //if(x<n) |
| 263 | // d[x]= MULT31_SHIFT15(d[x],FLOOR_fromdB_LOOKUP[y]); |
| 264 | |
| 265 | #if defined(ONLY_C) |
| 266 | do{ |
| 267 | *d = MULT31_SHIFT15(*d,*floor); |
| 268 | d++; |
| 269 | floor+=base; |
| 270 | err-=ady; |
| 271 | if(err<0){ |
| 272 | err+=adx; |
| 273 | floor+=1; |
| 274 | } |
| 275 | n--; |
| 276 | } while(n>0); |
| 277 | #else |
| 278 | render_lineARM(n,d,floor,base,err,adx,ady); |
| 279 | #endif |
| 280 | } |
| 281 | |
| 282 | int floor1_memosize(vorbis_info_floor *i){ |
| 283 | vorbis_info_floor1 *info=(vorbis_info_floor1 *)i; |
| 284 | return info->posts; |
| 285 | } |
| 286 | |
| 287 | static int quant_look[4]={256,128,86,64}; |
| 288 | |
| 289 | ogg_int32_t *floor1_inverse1(vorbis_dsp_state *vd,vorbis_info_floor *in, |
| 290 | ogg_int32_t *fit_value){ |
| 291 | vorbis_info_floor1 *info=(vorbis_info_floor1 *)in; |
| 292 | codec_setup_info *ci=(codec_setup_info *)vd->vi->codec_setup; |
| 293 | |
| 294 | int i,j,k; |
| 295 | codebook *books=ci->book_param; |
| 296 | int quant_q=quant_look[info->mult-1]; |
| 297 | |
| 298 | /* unpack wrapped/predicted values from stream */ |
| 299 | if(oggpack_read(&vd->opb,1)==1){ |
| 300 | fit_value[0]=oggpack_read(&vd->opb,ilog(quant_q-1)); |
| 301 | fit_value[1]=oggpack_read(&vd->opb,ilog(quant_q-1)); |
| 302 | |
| 303 | /* partition by partition */ |
| 304 | /* partition by partition */ |
| 305 | for(i=0,j=2;i<info->partitions;i++){ |
| 306 | int classv=info->partitionclass[i]; |
Andreas Huber | 1a7ca64 | 2010-05-07 10:37:02 -0700 | [diff] [blame] | 307 | int cdim=info->klass[classv].class_dim; |
| 308 | int csubbits=info->klass[classv].class_subs; |
Gloria Wang | 7913073 | 2010-02-08 14:41:04 -0800 | [diff] [blame] | 309 | int csub=1<<csubbits; |
| 310 | int cval=0; |
| 311 | |
| 312 | /* decode the partition's first stage cascade value */ |
| 313 | if(csubbits){ |
Andreas Huber | 1a7ca64 | 2010-05-07 10:37:02 -0700 | [diff] [blame] | 314 | cval=vorbis_book_decode(books+info->klass[classv].class_book,&vd->opb); |
Gloria Wang | 7913073 | 2010-02-08 14:41:04 -0800 | [diff] [blame] | 315 | |
| 316 | if(cval==-1)goto eop; |
| 317 | } |
| 318 | |
| 319 | for(k=0;k<cdim;k++){ |
Andreas Huber | 1a7ca64 | 2010-05-07 10:37:02 -0700 | [diff] [blame] | 320 | int book=info->klass[classv].class_subbook[cval&(csub-1)]; |
Gloria Wang | 7913073 | 2010-02-08 14:41:04 -0800 | [diff] [blame] | 321 | cval>>=csubbits; |
| 322 | if(book!=0xff){ |
| 323 | if((fit_value[j+k]=vorbis_book_decode(books+book,&vd->opb))==-1) |
| 324 | goto eop; |
| 325 | }else{ |
| 326 | fit_value[j+k]=0; |
| 327 | } |
| 328 | } |
| 329 | j+=cdim; |
| 330 | } |
| 331 | |
| 332 | /* unwrap positive values and reconsitute via linear interpolation */ |
| 333 | for(i=2;i<info->posts;i++){ |
| 334 | int predicted=render_point(info->postlist[info->loneighbor[i-2]], |
| 335 | info->postlist[info->hineighbor[i-2]], |
| 336 | fit_value[info->loneighbor[i-2]], |
| 337 | fit_value[info->hineighbor[i-2]], |
| 338 | info->postlist[i]); |
| 339 | int hiroom=quant_q-predicted; |
| 340 | int loroom=predicted; |
| 341 | int room=(hiroom<loroom?hiroom:loroom)<<1; |
| 342 | int val=fit_value[i]; |
| 343 | |
| 344 | if(val){ |
| 345 | if(val>=room){ |
| 346 | if(hiroom>loroom){ |
| 347 | val = val-loroom; |
| 348 | }else{ |
| 349 | val = -1-(val-hiroom); |
| 350 | } |
| 351 | }else{ |
| 352 | if(val&1){ |
| 353 | val= -((val+1)>>1); |
| 354 | }else{ |
| 355 | val>>=1; |
| 356 | } |
| 357 | } |
| 358 | |
| 359 | fit_value[i]=val+predicted; |
| 360 | fit_value[info->loneighbor[i-2]]&=0x7fff; |
| 361 | fit_value[info->hineighbor[i-2]]&=0x7fff; |
| 362 | |
| 363 | }else{ |
| 364 | fit_value[i]=predicted|0x8000; |
| 365 | } |
| 366 | |
| 367 | } |
| 368 | |
| 369 | return(fit_value); |
| 370 | } |
| 371 | eop: |
| 372 | return(NULL); |
| 373 | } |
| 374 | |
| 375 | int floor1_inverse2(vorbis_dsp_state *vd,vorbis_info_floor *in, |
| 376 | ogg_int32_t *fit_value,ogg_int32_t *out){ |
| 377 | vorbis_info_floor1 *info=(vorbis_info_floor1 *)in; |
| 378 | |
| 379 | codec_setup_info *ci=(codec_setup_info *)vd->vi->codec_setup; |
| 380 | int n=ci->blocksizes[vd->W]/2; |
| 381 | int j; |
| 382 | |
| 383 | if(fit_value){ |
| 384 | /* render the lines */ |
| 385 | int hx=0; |
| 386 | int lx=0; |
| 387 | int ly=fit_value[0]*info->mult; |
| 388 | for(j=1;j<info->posts;j++){ |
| 389 | int current=info->forward_index[j]; |
| 390 | int hy=fit_value[current]&0x7fff; |
| 391 | if(hy==fit_value[current]){ |
| 392 | |
| 393 | hy*=info->mult; |
| 394 | hx=info->postlist[current]; |
| 395 | |
| 396 | render_line(n,lx,hx,ly,hy,out); |
| 397 | |
| 398 | lx=hx; |
| 399 | ly=hy; |
| 400 | } |
| 401 | } |
| 402 | for(j=hx;j<n;j++)out[j]*=ly; /* be certain */ |
| 403 | return(1); |
| 404 | } |
| 405 | memset(out,0,sizeof(*out)*n); |
| 406 | return(0); |
| 407 | } |