prnt/hpcups/ModeDeltaPlus.cpp

   1 /*****************************************************************************\
   2   ModeDeltaPlus.cpp : Implementation of ModeDeltaPlus class
   3
   4   Copyright (c) 1996 - 2009, Hewlett-Packard Co.
   5   All rights reserved.
   6
   7   Redistribution and use in source and binary forms, with or without
   8   modification, are permitted provided that the following conditions
   9   are met:
  10   1. Redistributions of source code must retain the above copyright
  11      notice, this list of conditions and the following disclaimer.
  12   2. Redistributions in binary form must reproduce the above copyright
  13      notice, this list of conditions and the following disclaimer in the
  14      documentation and/or other materials provided with the distribution.
  15   3. Neither the name of Hewlett-Packard nor the names of its
  16      contributors may be used to endorse or promote products derived
  17      from this software without specific prior written permission.
  18
  19   THIS SOFTWARE IS PROVIDED BY THE AUTHOR "AS IS" AND ANY EXPRESS OR IMPLIED
  20   WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
  21   MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN
  22   NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  23   SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
  24   TO, PATENT INFRINGEMENT; PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
  25   OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
  26   ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  27   (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  28   THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29 \*****************************************************************************/
  30
  31 #include "ModeDeltaPlus.h"
  32
  33 ModeDeltaPlus::ModeDeltaPlus
  34 (
  35     unsigned int PlaneSize
  36 ) :
  37     Compressor(PlaneSize, true),
  38     pbyInputImageBuffer (NULL),
  39     pbySeedRow (NULL),
  40     m_bLastBand(false)
  41 {
  42     inputsize = PlaneSize;
  43     inputsize = ((inputsize + 7) / 8) * 8;
  44     m_lCurrCDRasterRow  = 0;
  45     m_lPrinterRasterRow = 0;
  46     iRastersReady = 0;
  47     m_bCompressed = false;
  48     m_compressedsize = 0;
  49     m_fRatio = 0;
  50 } // ModeDeltaPlus::ModeDeltaPlus
  51
  52 DRIVER_ERROR ModeDeltaPlus::Init()
  53 {
  54     // allocate a 2X compression buffer..
  55     compressBuf = new BYTE[2 * INDY_STRIP_HEIGHT * inputsize];
  56     if (compressBuf == NULL)
  57     {
  58         return ALLOCMEM_ERROR;
  59     }
  60     memset (compressBuf, 0x00, 2 * INDY_STRIP_HEIGHT * inputsize);
  61
  62     pbyInputImageBuffer = new BYTE[INDY_STRIP_HEIGHT * inputsize];
  63     if (pbyInputImageBuffer == NULL)
  64         return ALLOCMEM_ERROR;
  65     memset(pbyInputImageBuffer, 0x00, INDY_STRIP_HEIGHT * inputsize);
  66
  67     pbySeedRow = new BYTE[inputsize];
  68     if (pbySeedRow == NULL)
  69     {
  70         return ALLOCMEM_ERROR;
  71     }
  72     memset (pbySeedRow, 0, inputsize * sizeof (BYTE));
  73     return NO_ERROR;
  74 }
  75
  76 ModeDeltaPlus::~ModeDeltaPlus ()
  77 {
  78     if (pbyInputImageBuffer)
  79     {
  80         delete [] pbyInputImageBuffer;
  81         pbyInputImageBuffer = NULL;
  82     }
  83     if (pbySeedRow)
  84     {
  85         delete [] pbySeedRow;
  86         pbySeedRow = NULL;
  87     }
  88
  89 } // ModeDeltaPlus::~ModeDeltaPlus
  90
  91 /*
  92  * The maximum width of a line, which is limited by the amount of hardware
  93  * buffer space allocated to storing the seedrow.
  94  */
  95 #define ROW_LIMIT 7040
  96 /*
  97  * The maximum number of literals in a single command, not counting the first
  98  * pixel.  This is limited by the hardware buffer used to store a literal
  99  * string.  For real images, I expect a value of 64 would be a suitable
 100  * minimum.  The minimum compression ratio will be bounded by this.  Note also
 101  * that the software does not need any buffer for this, so there need be no
 102  * limit at all on a purely software implementation.  For the sake of enabling
 103  * a hardware implementation, I would strongly recommend leaving it in and set
 104  * to some reasonable value (say 1023 or 255).
 105  */
 106 #define LITERAL_LIMIT 511
 107
 108 /* These are set up this way to make it easy to change the predictions. */
 109 #define LTEST_W            col > 0
 110 #define LVAL_W(col)        cur_row[col-1]
 111 #define LTEST_NW           col > 0
 112 #define LVAL_NW(col)       seedrow[col-1]
 113 #define LTEST_WW           col > 1
 114 #define LVAL_WW(col)       cur_row[col-2]
 115 #define LTEST_NWW          col > 1
 116 #define LVAL_NWW(col)      seedrow[col-2]
 117 #define LTEST_NE           (col+1) < row_width
 118 #define LVAL_NE(col)       seedrow[col+1]
 119 #define LTEST_NEWCOL       1
 120 #define LVAL_NEWCOL(col)   new_color
 121 #define LTEST_CACHE        1
 122 #define LVAL_CACHE(col)    cache
 123
 124 #define LOC1TEST      LTEST_NE
 125 #define LOC1VAL(col)  LVAL_NE(col)
 126 #define LOC2TEST      LTEST_NW
 127 #define LOC2VAL(col)  LVAL_NW(col)
 128 #define LOC3TEST      LTEST_NEWCOL
 129 #define LOC3VAL(col)  LVAL_NEWCOL(col)
 130
 131 #define check(condition) if (!(condition)) return 0
 132
 133 #define write_comp_byte(val)           \
 134    check(outptr < pastoutmem);         \
 135    *outptr++ = (BYTE) val;
 136
 137 #define read_byte(val)                 \
 138    check(inmem < pastinmem);           \
 139    val = *inmem++;
 140
 141 #define encode_count(count, over, mem)         \
 142    if (count >= over)                          \
 143    {                                           \
 144       count -= over;                           \
 145       if (count <= (uint32_t) 253)             \
 146       {                                        \
 147          check(mem < pastoutmem);              \
 148          *mem++ = (BYTE) count;               \
 149       }                                        \
 150       else if (count <= (uint32_t) (254 + 255) ) \
 151       {                                        \
 152          check((mem+1) < pastoutmem);          \
 153          check( count >= 254 );                \
 154          check( (count - 254) <= 255 );        \
 155          *mem++ = (BYTE) 0xFE;                \
 156          *mem++ = (BYTE) (count - 254);       \
 157       }                                        \
 158       else                                     \
 159       {                                        \
 160          check((mem+2) < pastoutmem);          \
 161          check( count >= 255 );                \
 162          check( (count - 255) <= 65535 );      \
 163          count -= 255;                         \
 164          *mem++ = (BYTE) 0xFF;                \
 165          *mem++ = (BYTE) (count >> 8);        \
 166          *mem++ = (BYTE) (count & 0xFF);      \
 167       }                                        \
 168    }
 169 #define decode_count(count, over)              \
 170    if (count >= over)                          \
 171    {                                           \
 172       read_byte(inval);                        \
 173       count += (uint32_t) inval;                 \
 174       if (inval == (BYTE) 0xFE)               \
 175       {                                        \
 176          read_byte(inval);                     \
 177          count += (uint32_t) inval;              \
 178       }                                        \
 179       else if (inval == (BYTE) 0xFF)          \
 180       {                                        \
 181          read_byte(inval);                     \
 182          count += (((uint32_t) inval) << 8);     \
 183          read_byte(inval);                     \
 184          count += (uint32_t) inval;              \
 185       }                                        \
 186    }
 187
 188 #define bytes_for_count(count, over) \
 189   ( (count >= 255) ? 3 : (count >= over) ? 1 : 0 )
 190
 191
 192 /* The number of bytes we should be greater than to call memset/memcpy */
 193 #define memutil_thresh 15
 194
 195 BYTE* ModeDeltaPlus::encode_header(BYTE* outptr, const BYTE* pastoutmem, uint32_t isrun, uint32_t location, uint32_t seedrow_count, uint32_t run_count, const BYTE new_color)
 196 {
 197     uint32_t byte;
 198
 199     check (location < 4);
 200     check( (isrun == 0) || (isrun == 1) );
 201
 202     /* encode "literal" in command byte */
 203     byte = (isrun << 7) | (location << 5);
 204
 205     /* write out number of seedrow bytes to copy */
 206     if (seedrow_count > 2)
 207         byte |= (0x03 << 3);
 208     else
 209         byte |= (seedrow_count << 3);
 210
 211     if (run_count > 6)
 212         byte |= 0x07;
 213     else
 214         byte |= run_count;
 215
 216     /* write out command byte */
 217     write_comp_byte(byte);
 218
 219     /* macro to write count if it's 3 or more */
 220     encode_count( seedrow_count, 3, outptr );
 221
 222     /* if required, write out color of first pixel */
 223     if (location == 0)
 224     {
 225         write_comp_byte( new_color );
 226     }
 227
 228     /* macro to write count if it's 7 or more */
 229     encode_count( run_count, 7, outptr );
 230
 231     return outptr;
 232 }
 233
 234 /******************************************************************************/
 235 /*                                COMPRESSION                                 */
 236 /******************************************************************************/
 237 bool ModeDeltaPlus::compress (BYTE   *outmem,
 238                               uint32_t  *outlen,
 239                               const     BYTE     *inmem,
 240                               const     uint32_t    row_width,
 241                               const     uint32_t    inheight,
 242                               uint32_t  horz_ht_dist)
 243 {
 244     register    BYTE     *outptr = outmem;
 245     register    uint32_t    col;
 246     const       BYTE     *seedrow;
 247     uint32_t                seedrow_count = 0;
 248     uint32_t                location = 0;
 249     BYTE                 new_color = (BYTE) 0xFF;
 250     const       BYTE     *cur_row;
 251     uint32_t                row;
 252     const       BYTE     *pastoutmem = outmem + *outlen;
 253     uint32_t                do_word_copies;
 254     /* Halftone distance must be 1-32 (but allow 0 == 1) */
 255     if (horz_ht_dist > 32)
 256     {
 257         return false;
 258     }
 259     if (horz_ht_dist < 1)
 260     {
 261        horz_ht_dist = 1;
 262     }
 263
 264     seedrow = pbySeedRow;
 265     do_word_copies = ((row_width % 4) == 0);
 266
 267     for (row = 0; row < inheight; row++)
 268     {
 269         cur_row = inmem + (row * row_width);
 270
 271         col = 0;
 272         while (col < row_width)
 273         {
 274             /* First look for seedrow copy */
 275             seedrow_count = 0;
 276             if (do_word_copies)
 277             {
 278                 /* Try a fast word-based search */
 279                 while (((col & 3) != 0) &&
 280                         (col < row_width) &&
 281                         (cur_row[col] == seedrow[col]))
 282                 {
 283                     seedrow_count++;
 284                     col++;
 285                 }
 286                 if ( (col & 3) == 0)
 287                 {
 288                     while (((col+3) < row_width) &&
 289                             *((const uint32_t*) (cur_row + col)) == *((const uint32_t*) (seedrow + col)))
 290                     {
 291                         seedrow_count += 4;
 292                         col += 4;
 293                     }
 294                 }
 295             }
 296             while ((col < row_width) && (cur_row[col] == seedrow[col]))
 297             {
 298                seedrow_count++;
 299                col++;
 300             }
 301
 302             /* It is possible that we have hit the end of the line already. */
 303             if (col == row_width)
 304             {
 305                 /* encode pure seed run as fake run */
 306                 outptr = encode_header(outptr, pastoutmem, 1 /*run*/, 1 /*location*/, seedrow_count, 0 /*runcount*/, (BYTE) 0 /*color*/);
 307                 /* exit the while loop for this row */
 308                 break;
 309             }
 310             check(col < row_width);
 311
 312             /* determine the prediction for the current pixel */
 313             if ( (LOC1TEST) && (cur_row[col] == LOC1VAL(col)) )
 314                 location = 1;
 315             else if ( (LOC2TEST) && (cur_row[col] == LOC2VAL(col)) )
 316                 location = 2;
 317             else if ( (LOC3TEST) && (cur_row[col] == LOC3VAL(col)) )
 318                 location = 3;
 319             else
 320             {
 321                 location = 0;
 322                 new_color = cur_row[col];
 323             }
 324
 325
 326             /* Look for a run */
 327             if (
 328                  ((col+1) < row_width)
 329                  &&
 330                  ((col+1) >= horz_ht_dist)
 331                  &&
 332                  (cur_row[col+1-horz_ht_dist] == cur_row[col+1])
 333                )
 334             {
 335                 /* We found a run.  Determine the length. */
 336                 uint32_t run_count = 0;   /* Actually 2 */
 337                 col++;
 338                 while ( ((col+1) < row_width) && (cur_row[col+1-horz_ht_dist] == cur_row[col+1]) )
 339                 {
 340                    run_count++;
 341                    col++;
 342                 }
 343                 col++;
 344                 outptr = encode_header(outptr, pastoutmem, 1 /*run*/, location, seedrow_count, run_count, new_color);
 345             }
 346
 347             else
 348
 349             /* We didn't find a run.  Encode literal(s). */
 350             {
 351                 uint32_t replacement_count = 0;   /* Actually 1 */
 352                 const BYTE* byte_array = cur_row + col + 1;
 353                 uint32_t i;
 354                 col++;
 355                 /*
 356                  * The (col+1) in this test is used because there is no need to
 357                  * check for literal breaks if this is the last byte of the row.
 358                  * Instead we just tack it on to our literal count at the end.
 359                  */
 360                 while ( (col+1) < row_width )
 361                 {
 362                     /*
 363                      * All cases that will break with 1 unit saved.  This
 364                      * should be the best breaking spots, since we will always
 365                      * gain with the break, but never break for no gain.  This
 366                      * leads to longer strings which is good for decomp speed.
 367                      */
 368                     if (
 369                          /* Seedrow ... */
 370                          (
 371                            (cur_row[col] == seedrow[col])
 372                            &&
 373                            (
 374                              /* 2 seedrows */
 375                              (
 376                                (cur_row[col+1] == seedrow[col+1])
 377                              )
 378                              ||
 379                              /* seedrow and predict */
 380                              (
 381                                (cur_row[col+1] == LVAL_NW(col+1))
 382                                ||
 383                                (cur_row[col+1] == LVAL_NEWCOL(col+1))
 384                              )
 385                              ||
 386                              (
 387                                ((col+2) < row_width)
 388                                &&
 389                                (
 390                                  /* seedrow and run */
 391                                  (\r
 392                                    ((col + 2) >= horz_ht_dist) &&
 393                                    (cur_row[col+2-horz_ht_dist] == cur_row[col+2])\r
 394                                  )
 395                                  ||
 396                                  /* seedrow and northeast predict */
 397                                  (cur_row[col+1] == LVAL_NE(col+1))
 398                                )
 399                              )
 400                            )
 401                          )
 402                          ||
 403                          /* Run ... */
 404                          (
 405                            (cur_row[col] != seedrow[col])
 406                            &&
 407                            ((col + 1) >= horz_ht_dist)
 408                            &&
 409                            (cur_row[col+1-horz_ht_dist] == cur_row[col+1])
 410                            &&
 411                            (
 412                              /* Run of 3 or more */
 413                              (
 414                                ((col+2) < row_width)
 415                                &&
 416                                ((col + 2) >= horz_ht_dist)
 417                                &&
 418                                (cur_row[col+2-horz_ht_dist] == cur_row[col+2])
 419                              )
 420                              ||
 421                              /* Predict first unit of run */
 422                              (cur_row[col] == LVAL_NE(col))
 423                              ||
 424                              (cur_row[col] == LVAL_NW(col))
 425                              ||
 426                              (cur_row[col] == LVAL_NEWCOL(col))
 427                            )
 428                          )
 429                        )
 430                         break;
 431
 432                     /* limited hardware buffer */
 433                     if (replacement_count >= LITERAL_LIMIT)
 434                         break;
 435
 436                     /* add another literal to the list */
 437                     replacement_count++;
 438                     col++;
 439                 }
 440
 441                 /* If almost at end of block, just extend the literal by one */
 442                 if ( (col+1) == row_width ) {
 443                    replacement_count++;
 444                    col++;
 445                 }
 446
 447                 outptr = encode_header(outptr, pastoutmem, 0 /*not run*/, location, seedrow_count, replacement_count, new_color);
 448
 449                 /* Copy bytes from the byte array.  If rc was 1, then we will
 450                  * have encoded a zero in the command byte, so nothing will be
 451                  * copied here (the 1 indicates the first pixel, which was
 452                  * written above or was predicted.  If rc is between 2 and 7,
 453                  * then a value between 1 and 6 will have been written in the
 454                  * command byte, and we will copy it directly.  If 8 or more,
 455                  * then we encode more counts, then finally copy all the values
 456                  * from byte_array.
 457                  */
 458
 459                 if (replacement_count > 0)
 460                 {
 461                     /* Now insert rc bytes of data from byte_array */
 462                     if (replacement_count > memutil_thresh)
 463                     {
 464                         check( (outptr + replacement_count) <= pastoutmem );
 465                         memcpy(outptr, byte_array, (size_t) replacement_count);
 466                         outptr += replacement_count;
 467                     }
 468                     else
 469                     {
 470                         for (i = 0; i < replacement_count; i++)
 471                         {
 472                             write_comp_byte( byte_array[i] );
 473                         }
 474                     }
 475                 }
 476             }
 477
 478         } /* end of column */
 479
 480         /* save current row as next row's seed row */
 481         seedrow = cur_row;
 482
 483     } /* end of row */
 484
 485     check( outptr <= pastoutmem );
 486     if (outptr > pastoutmem)
 487     {
 488        /* We're in big trouble -- we wrote PAST the end of their memory! */
 489        *outlen = 0;
 490        return 0;
 491     }
 492
 493     *outlen = (uint32_t) (outptr - outmem);
 494
 495     return 1;
 496 } /* end of deltaplus_compress2 */
 497
 498
 499 bool ModeDeltaPlus::Process
 500 (
 501     RASTERDATA* input
 502 )
 503 {
 504     if (input==NULL ||
 505         (input->rasterdata[COLORTYPE_COLOR]==NULL && input->rasterdata[COLORTYPE_BLACK]==NULL))    // flushing pipeline
 506     {
 507         return false;
 508     }
 509     if (input->rasterdata[COLORTYPE_COLOR])
 510     {
 511         if (m_lCurrCDRasterRow < INDY_STRIP_HEIGHT )
 512         {
 513             //Copy the data to m_SourceBitmap
 514             memcpy(pbyInputImageBuffer + m_lCurrCDRasterRow * inputsize, input->rasterdata[COLORTYPE_COLOR], input->rastersize[COLORTYPE_COLOR]);
 515             m_lCurrCDRasterRow ++;
 516         }
 517         if (m_lCurrCDRasterRow == INDY_STRIP_HEIGHT || m_bLastBand)
 518         {
 519             m_compressedsize = 2 * inputsize * INDY_STRIP_HEIGHT;
 520             bool bRet = compress (compressBuf,
 521                                   &m_compressedsize,
 522                                   pbyInputImageBuffer,
 523                                   inputsize,
 524                                   m_lCurrCDRasterRow,
 525                                   16
 526                                   );
 527             if (!bRet)
 528             {
 529                 memcpy (compressBuf, pbyInputImageBuffer, inputsize * INDY_STRIP_HEIGHT);
 530                 m_compressedsize = inputsize * INDY_STRIP_HEIGHT;
 531             }
 532             else
 533             {
 534                 m_bCompressed = true;
 535             }
 536
 537             memset(pbyInputImageBuffer, 0x00, inputsize * INDY_STRIP_HEIGHT);
 538
 539             m_lPrinterRasterRow += m_lCurrCDRasterRow;
 540             m_lCurrBlockHeight = m_lCurrCDRasterRow;
 541             m_lCurrCDRasterRow = 0;
 542             iRastersReady = 1;
 543             m_bLastBand = false;
 544         }
 545         else
 546         {
 547             return false;
 548         }
 549     }
 550     return true;
 551 } //Process
 552
 553 bool ModeDeltaPlus::NextOutputRaster(RASTERDATA &next_raster)
 554 {
 555     if (iRastersReady==0)
 556         return false;
 557
 558     next_raster.rastersize[COLORTYPE_COLOR] =  m_compressedsize;
 559     if (m_compressedsize > 0)
 560     {
 561         next_raster.rasterdata[COLORTYPE_COLOR] =  compressBuf;
 562     }
 563     next_raster.rastersize[COLORTYPE_BLACK] = 0;
 564     next_raster.rasterdata[COLORTYPE_BLACK] = NULL;
 565     iRastersReady=0;
 566     return true;
 567 }
 568