Source for gnu.javax.imageio.jpeg.ZigZag

   1: /* ZigZag.java --
   2:    Copyright (C)  2005  Free Software Foundation, Inc.
   3: 
   4: This file is part of GNU Classpath.
   5: 
   6: GNU Classpath is free software; you can redistribute it and/or modify
   7: it under the terms of the GNU General Public License as published by
   8: the Free Software Foundation; either version 2, or (at your option)
   9: any later version.
  10: 
  11: GNU Classpath is distributed in the hope that it will be useful, but
  12: WITHOUT ANY WARRANTY; without even the implied warranty of
  13: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14: General Public License for more details.
  15: 
  16: You should have received a copy of the GNU General Public License
  17: along with GNU Classpath; see the file COPYING.  If not, write to the
  18: Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  19: 02110-1301 USA.
  20: 
  21: Linking this library statically or dynamically with other modules is
  22: making a combined work based on this library.  Thus, the terms and
  23: conditions of the GNU General Public License cover the whole
  24: combination.
  25: 
  26: As a special exception, the copyright holders of this library give you
  27: permission to link this library with independent modules to produce an
  28: executable, regardless of the license terms of these independent
  29: modules, and to copy and distribute the resulting executable under
  30: terms of your choice, provided that you also meet, for each linked
  31: independent module, the terms and conditions of the license of that
  32: module.  An independent module is a module which is not derived from
  33: or based on this library.  If you modify this library, you may extend
  34: this exception to your version of the library, but you are not
  35: obligated to do so.  If you do not wish to do so, delete this
  36: exception statement from your version. */
  37: 
  38: package gnu.javax.imageio.jpeg;
  39: 
  40: /**
  41:  * This class implements the Zig Zag Algorithm on any array with
  42:  * the same amount of rows and columns. It takes a matrix and in turn builds an
  43:  * encoded byte array (or double array) from it. The adverse is also true, this
  44:  * will take a byte or double array and build a matrix based on the zig zag
  45:  * algorithm.
  46:  * <p>This is used exclusively in the JPEG DCT encoding.</p>
  47:  */
  48: public class ZigZag
  49: {
  50:   public final static boolean ZIGZAG_FORWARD = true;
  51:   public final static boolean ZIGZAG_BACKWARD = false;
  52:   public final static int ZIGZAG_8X8_MAP[] =
  53:   {
  54:    0,   1,  8, 16,  9,  2,  3, 10,
  55:    17, 24, 32, 25, 18, 11,  4,  5,
  56:    12, 19, 26, 33, 40, 48, 41, 34,
  57:    27, 20, 13,  6,  7, 14, 21, 28,
  58:    35, 42, 49, 56, 57, 50, 43, 36,
  59:    29, 22, 15, 23, 30, 37, 44, 51,
  60:    58, 59, 52, 45, 38, 31, 39, 46,
  61:    53, 60, 61, 54, 47, 55, 62, 63
  62:   };
  63: 
  64:   /**
  65:    * Encodes a matrix of equal width and height to a byte array.
  66:    *
  67:    * @param matrix
  68:    *
  69:    * @return
  70:    */
  71:   public static byte[] encode(byte[][] matrix)
  72:   {
  73:     byte[] buffer = new byte[matrix.length ^ 2];
  74:     boolean direction = ZigZag.ZIGZAG_FORWARD;
  75:     int x = 0, y = 0, index = 0;
  76:     for (int zigIndex = 0; zigIndex < (matrix.length * 2 - 1);
  77:          zigIndex++, direction = !direction)
  78:       {
  79:         if (direction == ZigZag.ZIGZAG_FORWARD)
  80:           {
  81:             while (x >= 0 && y != matrix.length)
  82:               {
  83:                 if (x == matrix.length)
  84:                   {
  85:                     x--;
  86:                     y++;
  87:                   }
  88:                 buffer[index] = matrix[x][y];
  89:                 y++;
  90:                 x--;
  91:                 index++;
  92:               }
  93:             x++;
  94:           }
  95:         else
  96:           {
  97:             while (y >= 0 && x != matrix.length)
  98:               {
  99:                 if (y == matrix.length)
 100:                   {
 101:                     y--;
 102:                     x++;
 103:                   }
 104:                 buffer[index] = matrix[x][y];
 105:                 y--;
 106:                 x++;
 107:                 index++;
 108:               }
 109:             y++;
 110:           }
 111:       }
 112:     return (buffer);
 113:   }
 114: 
 115:   /**
 116:    * Encodes a matrix of equal width and height to a double array
 117:    *
 118:    * @param matrix
 119:    *
 120:    * @return
 121:    */
 122:   public static double[] encode(double[][] matrix)
 123:   {
 124:     double[] buffer = new double[matrix.length * matrix.length];
 125:     boolean direction = ZigZag.ZIGZAG_FORWARD;
 126:     int x = 0, y = 0, index = 0;
 127:     for (int zigIndex = 0; zigIndex < (matrix.length * 2 - 1);
 128:          zigIndex++, direction = !direction)
 129:       {
 130:         if (direction == ZigZag.ZIGZAG_FORWARD)
 131:           {
 132:             while (x >= 0 && y != matrix.length)
 133:               {
 134:                 if (x == matrix.length)
 135:                   {
 136:                     x--;
 137:                     y++;
 138:                   }
 139:                 buffer[index] = matrix[x][y];
 140:                 y++;
 141:                 x--;
 142:                 index++;
 143:               }
 144:             x++;
 145:           }
 146:         else
 147:           {
 148:             while (y >= 0 && x != matrix.length)
 149:               {
 150:                 if (y == matrix.length)
 151:                   {
 152:                     y--;
 153:                     x++;
 154:                   }
 155:                 buffer[index] = matrix[x][y];
 156:                 y--;
 157:                 x++;
 158:                 index++;
 159:               }
 160:             y++;
 161:           }
 162:       }
 163:     return (buffer);
 164:   }
 165: 
 166:   /**
 167:    * Encodes a matrix of equal width and height to a float array
 168:    *
 169:    * @param matrix
 170:    *
 171:    * @return
 172:    */
 173:   public static float[] encode(float[][] matrix)
 174:   {
 175:     float[] buffer = new float[matrix.length * matrix.length];
 176:     boolean direction = ZigZag.ZIGZAG_FORWARD;
 177:     int x = 0, y = 0, index = 0;
 178:     for (int zigIndex = 0; zigIndex < (matrix.length * 2 - 1);
 179:          zigIndex++, direction = !direction)
 180:       {
 181:         if (direction == ZigZag.ZIGZAG_FORWARD)
 182:           {
 183:             while (x >= 0 && y != matrix.length)
 184:               {
 185:                 if (x == matrix.length)
 186:                   {
 187:                     x--;
 188:                     y++;
 189:                   }
 190:                 buffer[index] = matrix[x][y];
 191:                 y++;
 192:                 x--;
 193:                 index++;
 194:               }
 195:             x++;
 196:           }
 197:         else
 198:           {
 199:             while (y >= 0 && x != matrix.length)
 200:               {
 201:                 if (y == matrix.length)
 202:                   {
 203:                     y--;
 204:                     x++;
 205:                   }
 206:                 buffer[index] = matrix[x][y];
 207:                 y--;
 208:                 x++;
 209:                 index++;
 210:               }
 211:             y++;
 212:           }
 213:       }
 214:     return (buffer);
 215:   }
 216: 
 217:   /**
 218:    * Encodes a matrix of equal width and height to a float array
 219:    *
 220:    * @param matrix
 221:    *
 222:    * @return
 223:    */
 224:   public static short[] encode(short[][] matrix)
 225:   {
 226:     short[] buffer = new short[matrix.length * matrix.length];
 227:     boolean direction = ZigZag.ZIGZAG_FORWARD;
 228:     int x = 0, y = 0, index = 0;
 229:     for (int zigIndex = 0; zigIndex < (matrix.length * 2 - 1);
 230:          zigIndex++, direction = !direction)
 231:       {
 232:         if (direction == ZigZag.ZIGZAG_FORWARD)
 233:           {
 234:             while (x >= 0 && y != matrix.length)
 235:               {
 236:                 if (x == matrix.length)
 237:                   {
 238:                     x--;
 239:                     y++;
 240:                   }
 241:                 buffer[index] = matrix[x][y];
 242:                 y++;
 243:                 x--;
 244:                 index++;
 245:               }
 246:             x++;
 247:           }
 248:         else
 249:           {
 250:             while (y >= 0 && x != matrix.length)
 251:               {
 252:                 if (y == matrix.length)
 253:                   {
 254:                     y--;
 255:                     x++;
 256:                   }
 257:                 buffer[index] = matrix[x][y];
 258:                 y--;
 259:                 x++;
 260:                 index++;
 261:               }
 262:             y++;
 263:           }
 264:       }
 265:     return (buffer);
 266:   }
 267: 
 268:   /**
 269:    * Convert a double array into a matrix with the same amount of columns and
 270:    * rows with length sqrt(double array length)
 271:    *
 272:    * @param data
 273:    *
 274:    * @return
 275:    */
 276:   public static double[][] decode(double[] data)
 277:   {
 278:     return decode(data, (int) Math.sqrt(data.length),
 279:                   (int) Math.sqrt(data.length));
 280:   }
 281: 
 282:   /**
 283:    * Convert a byte array into a matrix with the same amount of columns and
 284:    * rows with length sqrt(double array length)
 285:    *
 286:    * @param data
 287:    *
 288:    * @return
 289:    */
 290:   public static byte[][] decode(byte[] data)
 291:   {
 292:     return decode(data, (int) Math.sqrt(data.length),
 293:                   (int) Math.sqrt(data.length));
 294:   }
 295: 
 296:   public static int[][] decode(int[] data)
 297:   {
 298:     return decode(data, (int) Math.sqrt(data.length),
 299:                   (int) Math.sqrt(data.length));
 300:   }
 301: 
 302:   public static byte[][] decode(byte[] data, int width, int height)
 303:   {
 304:     byte[][] buffer = new byte[height][width];
 305: 
 306:     for (int v = 0; v < height; v++)
 307:       for (int z = 0; z < width; z++)
 308:         buffer[v][z] = 11;
 309: 
 310:     boolean dir = ZigZag.ZIGZAG_FORWARD;
 311:     int xindex = 0, yindex = 0, dataindex = 0;
 312: 
 313:     while (xindex < width && yindex < height && dataindex < data.length)
 314:       {
 315:         buffer[yindex][xindex] = data[dataindex];
 316:         dataindex++;
 317: 
 318:         if (dir == ZigZag.ZIGZAG_FORWARD)
 319:           {
 320:             if (yindex == 0 || xindex == (width - 1))
 321:               {
 322:                 dir = ZigZag.ZIGZAG_BACKWARD;
 323:                 if (xindex == (width - 1))
 324:                   yindex++;
 325:                 else
 326:                   xindex++;
 327:               }
 328:             else
 329:               {
 330:                 yindex--;
 331:                 xindex++;
 332:               }
 333:           }
 334:         else
 335:           { /* Backwards */
 336:             if (xindex == 0 || yindex == (height - 1))
 337:               {
 338:                 dir = ZigZag.ZIGZAG_FORWARD;
 339:                 if (yindex == (height - 1))
 340:                   xindex++;
 341:                 else
 342:                   yindex++;
 343:               }
 344:             else
 345:               {
 346:                 yindex++;
 347:                 xindex--;
 348:               }
 349:           }
 350:       }
 351:     return (buffer);
 352:   }
 353: 
 354:   public static double[][] decode(double[] data, int width, int height)
 355:   {
 356:     double[][] buffer = new double[height][width];
 357: 
 358:     for (int v = 0; v < height; v++)
 359:       for (int z = 0; z < width; z++)
 360:         buffer[v][z] = 11;
 361: 
 362:     boolean dir = ZigZag.ZIGZAG_FORWARD;
 363:     int xindex = 0, yindex = 0, dataindex = 0;
 364: 
 365:     while (xindex < width && yindex < height && dataindex < data.length)
 366:       {
 367:         buffer[yindex][xindex] = data[dataindex];
 368:         dataindex++;
 369:         System.err.println("Setting " + dataindex + " to row: " + yindex
 370:                            + " column: " + xindex + " yourval:"
 371:                            + (yindex*8+xindex));
 372:         if (dir == ZigZag.ZIGZAG_FORWARD)
 373:           {
 374:             if (yindex == 0 || xindex == (width - 1))
 375:               {
 376:                 dir = ZigZag.ZIGZAG_BACKWARD;
 377:                 if (xindex == (width - 1))
 378:                   yindex++;
 379:                 else
 380:                   xindex++;
 381:               }
 382:             else
 383:               {
 384:                 yindex--;
 385:                 xindex++;
 386:               }
 387:           }
 388:         else
 389:           { /* Backwards */
 390:             if (xindex == 0 || yindex == (height - 1))
 391:               {
 392:                 dir = ZigZag.ZIGZAG_FORWARD;
 393:                 if (yindex == (height - 1))
 394:                   xindex++;
 395:                 else
 396:                   yindex++;
 397:               }
 398:             else
 399:               {
 400:                 yindex++;
 401:                 xindex--;
 402:               }
 403:           }
 404:       }
 405:     return (buffer);
 406:   }
 407: 
 408:   public static float[][] decode(float[] data, int width, int height)
 409:   {
 410:     float[][] buffer = new float[height][width];
 411: 
 412:     for (int v = 0; v < height; v++)
 413:       for (int z = 0; z < width; z++)
 414:         buffer[v][z] = 11;
 415: 
 416:     boolean dir = ZigZag.ZIGZAG_FORWARD;
 417:     int xindex = 0, yindex = 0, dataindex = 0;
 418: 
 419:     while (xindex < width && yindex < height && dataindex < data.length)
 420:       {
 421:         buffer[yindex][xindex] = data[dataindex];
 422:         dataindex++;
 423: 
 424:         if (dir == ZigZag.ZIGZAG_FORWARD)
 425:           {
 426:             if (yindex == 0 || xindex == (width - 1))
 427:               {
 428:                 dir = ZigZag.ZIGZAG_BACKWARD;
 429:                 if (xindex == (width - 1))
 430:                   yindex++;
 431:                 else
 432:                   xindex++;
 433:               }
 434:             else
 435:               {
 436:                 yindex--;
 437:                 xindex++;
 438:               }
 439:           }
 440:         else
 441:           { /* Backwards */
 442:             if (xindex == 0 || yindex == (height - 1))
 443:               {
 444:                 dir = ZigZag.ZIGZAG_FORWARD;
 445:                 if (yindex == (height - 1))
 446:                   xindex++;
 447:                 else
 448:                   yindex++;
 449:               }
 450:             else
 451:               {
 452:                 yindex++;
 453:                 xindex--;
 454:               }
 455:           }
 456:       }
 457:     return (buffer);
 458:   }
 459: 
 460:   public static int[][] decode(int[] data, int width, int height)
 461:   {
 462:     int[][] buffer = new int[height][width];
 463: 
 464:     for (int v = 0; v < height; v++)
 465:       for (int z = 0; z < width; z++)
 466:         buffer[v][z] = 11;
 467: 
 468:     boolean dir = ZigZag.ZIGZAG_FORWARD;
 469:     int xindex = 0, yindex = 0, dataindex = 0;
 470: 
 471:     while (xindex < width && yindex < height && dataindex < data.length)
 472:       {
 473:         buffer[yindex][xindex] = data[dataindex];
 474:         dataindex++;
 475: 
 476:         if (dir == ZigZag.ZIGZAG_FORWARD)
 477:           {
 478:             if (yindex == 0 || xindex == (width - 1))
 479:               {
 480:                 dir = ZigZag.ZIGZAG_BACKWARD;
 481:                 if (xindex == (width - 1))
 482:                   yindex++;
 483:                 else
 484:                   xindex++;
 485:               }
 486:             else
 487:               {
 488:                 yindex--;
 489:                 xindex++;
 490:               }
 491:           }
 492:         else
 493:           { /* Backwards */
 494:             if (xindex == 0 || yindex == (height - 1))
 495:               {
 496:                 dir = ZigZag.ZIGZAG_FORWARD;
 497:                 if (yindex == (height - 1))
 498:                   xindex++;
 499:                 else
 500:                   yindex++;
 501:               }
 502:             else
 503:               {
 504:                 yindex++;
 505:                 xindex--;
 506:               }
 507:           }
 508:       }
 509:     return (buffer);
 510:   }
 511: 
 512:   public static double[][] decode8x8_map(double input[])
 513:   {
 514:     double[][] output = new double[8][8];
 515:     for(int i=0; i < 64 ; i++)
 516:       output[ZIGZAG_8X8_MAP[i]/8][ZIGZAG_8X8_MAP[i]%8] = input[i];
 517:     return (output);
 518:   }
 519: 
 520: }