sys/src/cmd/scat/qtree.c

   1 #include        <u.h>
   2 #include        <libc.h>
   3 #include        <bio.h>
   4 #include        "sky.h"
   5
   6 static void     qtree_expand(Biobuf*, uchar*, int, int, uchar*);
   7 static void     qtree_copy(uchar*, int, int, uchar*, int);
   8 static void     qtree_bitins(uchar*, int, int, Pix*, int, int);
   9 static void     read_bdirect(Biobuf*, Pix*, int, int, int, uchar*, int);
  10
  11 void
  12 qtree_decode(Biobuf *infile, Pix *a, int n, int nqx, int nqy, int nbitplanes)
  13 {
  14         int log2n, k, bit, b, nqmax;
  15         int nx,ny,nfx,nfy,c;
  16         int nqx2, nqy2;
  17         unsigned char *scratch;
  18
  19         /*
  20          * log2n is log2 of max(nqx,nqy) rounded up to next power of 2
  21          */
  22         nqmax = nqy;
  23         if(nqx > nqmax)
  24                 nqmax = nqx;
  25         log2n = log(nqmax)/LN2+0.5;
  26         if (nqmax > (1<<log2n))
  27                 log2n++;
  28
  29         /*
  30          * allocate scratch array for working space
  31          */
  32         nqx2 = (nqx+1)/2;
  33         nqy2 = (nqy+1)/2;
  34         scratch = (uchar*)malloc(nqx2*nqy2);
  35         if(scratch == nil) {
  36                 fprint(2, "qtree_decode: insufficient memory\n");
  37                 exits("memory");
  38         }
  39
  40         /*
  41          * now decode each bit plane, starting at the top
  42          * A is assumed to be initialized to zero
  43          */
  44         for(bit = nbitplanes-1; bit >= 0; bit--) {
  45                 /*
  46                  * Was bitplane was quadtree-coded or written directly?
  47                  */
  48                 b = input_nybble(infile);
  49                 if(b == 0) {
  50                         /*
  51                          * bit map was written directly
  52                          */
  53                         read_bdirect(infile, a, n, nqx, nqy, scratch, bit);
  54                 } else
  55                 if(b != 0xf) {
  56                         fprint(2, "qtree_decode: bad format code %x\n",b);
  57                         exits("format");
  58                 } else {
  59                         /*
  60                          * bitmap was quadtree-coded, do log2n expansions
  61                          * read first code
  62                          */
  63
  64                         scratch[0] = input_huffman(infile);
  65
  66                         /*
  67                          * do log2n expansions, reading codes from file as necessary
  68                          */
  69                         nx = 1;
  70                         ny = 1;
  71                         nfx = nqx;
  72                         nfy = nqy;
  73                         c = 1<<log2n;
  74                         for(k = 1; k<log2n; k++) {
  75                                 /*
  76                                  * this somewhat cryptic code generates the sequence
  77                                  * n[k-1] = (n[k]+1)/2 where n[log2n]=nqx or nqy
  78                                  */
  79                                 c = c>>1;
  80                                 nx = nx<<1;
  81                                 ny = ny<<1;
  82                                 if(nfx <= c)
  83                                         nx--;
  84                                 else
  85                                         nfx -= c;
  86                                 if(nfy <= c)
  87                                         ny--;
  88                                 else
  89                                         nfy -= c;
  90                                 qtree_expand(infile, scratch, nx, ny, scratch);
  91                         }
  92
  93                         /*
  94                          * copy last set of 4-bit codes to bitplane bit of array a
  95                          */
  96                         qtree_bitins(scratch, nqx, nqy, a, n, bit);
  97                 }
  98         }
  99         free(scratch);
 100 }
 101
 102 /*
 103  * do one quadtree expansion step on array a[(nqx+1)/2,(nqy+1)/2]
 104  * results put into b[nqx,nqy] (which may be the same as a)
 105  */
 106 static
 107 void
 108 qtree_expand(Biobuf *infile, uchar *a, int nx, int ny, uchar *b)
 109 {
 110         uchar *b1;
 111
 112         /*
 113          * first copy a to b, expanding each 4-bit value
 114          */
 115         qtree_copy(a, nx, ny, b, ny);
 116
 117         /*
 118          * now read new 4-bit values into b for each non-zero element
 119          */
 120         b1 = &b[nx*ny];
 121         while(b1 > b) {
 122                 b1--;
 123                 if(*b1 != 0)
 124                         *b1 = input_huffman(infile);
 125         }
 126 }
 127
 128 /*
 129  * copy 4-bit values from a[(nx+1)/2,(ny+1)/2] to b[nx,ny], expanding
 130  * each value to 2x2 pixels
 131  * a,b may be same array
 132  */
 133 static
 134 void
 135 qtree_copy(uchar *a, int nx, int ny, uchar *b, int n)
 136 {
 137         int i, j, k, nx2, ny2;
 138         int s00, s10;
 139
 140         /*
 141          * first copy 4-bit values to b
 142          * start at end in case a,b are same array
 143          */
 144         nx2 = (nx+1)/2;
 145         ny2 = (ny+1)/2;
 146         k = ny2*(nx2-1) + ny2-1;        /* k   is index of a[i,j] */
 147         for (i = nx2-1; i >= 0; i--) {
 148                 s00 = 2*(n*i+ny2-1);    /* s00 is index of b[2*i,2*j] */
 149                 for (j = ny2-1; j >= 0; j--) {
 150                         b[s00] = a[k];
 151                         k -= 1;
 152                         s00 -= 2;
 153                 }
 154         }
 155
 156         /*
 157          * now expand each 2x2 block
 158          */
 159         for(i = 0; i<nx-1; i += 2) {
 160                 s00 = n*i;                              /* s00 is index of b[i,j] */
 161                 s10 = s00+n;                            /* s10 is index of b[i+1,j] */
 162                 for(j = 0; j<ny-1; j += 2) {
 163                         b[s10+1] =  b[s00]     & 1;
 164                         b[s10  ] = (b[s00]>>1) & 1;
 165                         b[s00+1] = (b[s00]>>2) & 1;
 166                         b[s00  ] = (b[s00]>>3) & 1;
 167                         s00 += 2;
 168                         s10 += 2;
 169                 }
 170                 if(j < ny) {
 171                         /*
 172                          * row size is odd, do last element in row
 173                          * s00+1, s10+1 are off edge
 174                          */
 175                         b[s10  ] = (b[s00]>>1) & 1;
 176                         b[s00  ] = (b[s00]>>3) & 1;
 177                 }
 178         }
 179         if(i < nx) {
 180                 /*
 181                  * column size is odd, do last row
 182                  * s10, s10+1 are off edge
 183                  */
 184                 s00 = n*i;
 185                 for (j = 0; j<ny-1; j += 2) {
 186                         b[s00+1] = (b[s00]>>2) & 1;
 187                         b[s00  ] = (b[s00]>>3) & 1;
 188                         s00 += 2;
 189                 }
 190                 if(j < ny) {
 191                         /*
 192                          * both row and column size are odd, do corner element
 193                          * s00+1, s10, s10+1 are off edge
 194                          */
 195                         b[s00  ] = (b[s00]>>3) & 1;
 196                 }
 197         }
 198 }
 199
 200 /*
 201  * Copy 4-bit values from a[(nx+1)/2,(ny+1)/2] to b[nx,ny], expanding
 202  * each value to 2x2 pixels and inserting into bitplane BIT of B.
 203  * A,B may NOT be same array (it wouldn't make sense to be inserting
 204  * bits into the same array anyway.)
 205  */
 206 static
 207 void
 208 qtree_bitins(uchar *a, int nx, int ny, Pix *b, int n, int bit)
 209 {
 210         int i, j;
 211         Pix *s00, *s10;
 212         Pix px;
 213
 214         /*
 215          * expand each 2x2 block
 216          */
 217         for(i=0; i<nx-1; i+=2) {
 218                 s00 = &b[n*i];                  /* s00 is index of b[i,j] */
 219                 s10 = s00+n;                    /* s10 is index of b[i+1,j] */
 220                 for(j=0; j<ny-1; j+=2) {
 221                         px = *a++;
 222                         s10[1] |= ( px     & 1) << bit;
 223                         s10[0] |= ((px>>1) & 1) << bit;
 224                         s00[1] |= ((px>>2) & 1) << bit;
 225                         s00[0] |= ((px>>3) & 1) << bit;
 226                         s00 += 2;
 227                         s10 += 2;
 228                 }
 229                 if(j < ny) {
 230                         /*
 231                          * row size is odd, do last element in row
 232                          * s00+1, s10+1 are off edge
 233                          */
 234                         px = *a++;
 235                         s10[0] |= ((px>>1) & 1) << bit;
 236                         s00[0] |= ((px>>3) & 1) << bit;
 237                 }
 238         }
 239         if(i < nx) {
 240                 /*
 241                  * column size is odd, do last row
 242                  * s10, s10+1 are off edge
 243                  */
 244                 s00 = &b[n*i];
 245                 for(j=0; j<ny-1; j+=2) {
 246                         px = *a++;
 247                         s00[1] |= ((px>>2) & 1) << bit;
 248                         s00[0] |= ((px>>3) & 1) << bit;
 249                         s00 += 2;
 250                 }
 251                 if(j < ny) {
 252                         /*
 253                          * both row and column size are odd, do corner element
 254                          * s00+1, s10, s10+1 are off edge
 255                          */
 256                         s00[0] |= ((*a>>3) & 1) << bit;
 257                 }
 258         }
 259 }
 260
 261 static
 262 void
 263 read_bdirect(Biobuf *infile, Pix *a, int n, int nqx, int nqy, uchar *scratch, int bit)
 264 {
 265         int i;
 266
 267         /*
 268          * read bit image packed 4 pixels/nybble
 269          */
 270         for(i = 0; i < ((nqx+1)/2) * ((nqy+1)/2); i++) {
 271                 scratch[i] = input_nybble(infile);
 272         }
 273
 274         /*
 275          * insert in bitplane BIT of image A
 276          */
 277         qtree_bitins(scratch, nqx, nqy, a, n, bit);
 278 }