ip/xgray2bi.c

   1 /* libhpojip -- HP OfficeJet image-processing library. */
   2
   3 /* Copyright (C) 1995-2002 Hewlett-Packard Company
   4  *
   5  * This program is free software; you can redistribute it and/or
   6  * modify it under the terms of the GNU General Public License as
   7  * published by the Free Software Foundation; either version 2 of the
   8  * License, or (at your option) any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful, but
  11  * is provided AS IS, WITHOUT ANY WARRANTY; without even the implied
  12  * warranty of MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, and
  13  * NON-INFRINGEMENT.  See the GNU General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License
  16  * along with this program; if not, write to the Free Software
  17  * Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  18  * MA 02111-1307, USA.
  19  *
  20  * In addition, as a special exception, Hewlett-Packard Company
  21  * gives permission to link the code of this program with any
  22  * version of the OpenSSL library which is distributed under a
  23  * license identical to that listed in the included LICENSE.OpenSSL
  24  * file, and distribute linked combinations including the two.
  25  * You must obey the GNU General Public License in all respects
  26  * for all of the code used other than OpenSSL.  If you modify
  27  * this file, you may extend this exception to your version of the
  28  * file, but you are not obligated to do so.  If you do not wish to
  29  * do so, delete this exception statement from your version.
  30  */
  31
  32 /* Original author: Mark Overton and others.
  33  *
  34  * Ported to Linux by David Paschal.
  35  */
  36
  37 /******************************************************************************\
  38  *
  39  * xgray2bi.c - Error-diffuser and thresholder that's designed to be fast
  40  *
  41  ******************************************************************************
  42  *
  43  * Jan  1998 Mark Overton -- ported code into an xform driver
  44  * June 1995 Mark Overton -- developed and benchmarked algorithm
  45  *
  46  * Name of Global Jump-Table:
  47  *
  48  *    gray2biTbl
  49  *
  50  * Items in aXformInfo array passed into setXformSpec:
  51  *
  52  *    aXformInfo[IP_GRAY_2_BI_THRESHOLD] = Threshold.
  53  *        If threshold is zero, error-diffusion is done.
  54  *        If non-zero, it is the black/white threshold:
  55  *        A gray pixel >= to threshold becomes white, else black.
  56  *
  57  * Capabilities and Limitations:
  58  *
  59  *    Inputs rows of 8-bit gray pixels, and outputs rows of bi-level pixels.
  60  *    The formats are the standard raw formats described in hpojip.h.
  61  *    The error-diffusion weights are perturbed by small internally-generated
  62  *    amounts to break up any pixel patterns that would otherwise occur.
  63  *
  64  * Default Input Traits, and Output Traits:
  65  *
  66  *          trait             default input             output
  67  *    -------------------  ---------------------  ------------------------
  68  *    iPixelsPerRow         * passed into output   same as default input
  69  *    iBitsPerPixel         * must be 8            1
  70  *    iComponentsPerPixel   * must be 1            1
  71  *    lHorizDPI               passed into output   same as default input
  72  *    lVertDPI                passed into output   same as default input
  73  *    lNumRows                passed into output   same as default input
  74  *    iNumPages               passed into output   same as default input
  75  *    iPageNum                passed into output   same as default input
  76  *
  77  *    Above, a "*" by an item indicates it must be valid (not negative).
  78  *
  79  * Error-diffusion timings (seconds for one page):
  80  *
  81  * 386-33 486-33 486-66 P-90  735  image dim               task
  82  * ------ ------ ------ ---- ----- --------- ---------------------------------
  83  *  21.6    9.0    4.4  2.3   1.4  1728x2200  200x200 fax in photo mode
  84  *  43.    17.9    8.9  4.6   2.9  2400x3150  300x300 local copy, 1/4" margins
  85  *  86.    36.    17.9  9.3   5.7  4800x3150  600x300 local copy, 1/4" margins
  86  *
  87 \******************************************************************************/
  88
  89 #include "hpip.h"
  90 #include "ipdefs.h"
  91 #include "string.h"    /* for memset and memcpy */
  92
  93
  94 #if 0
  95     #include "stdio.h"
  96     #include <tchar.h>
  97
  98     #define PRINT(msg,arg1,arg2) \
  99         _ftprintf(stderr, msg, (int)arg1, (int)arg2)
 100 #else
 101     #define PRINT(msg,arg1,arg2)
 102 #endif
 103
 104 #define CHECK_VALUE 0x1ce5ca7e
 105
 106
 107 typedef struct {
 108     IP_IMAGE_TRAITS inTraits; /* traits of the input image */
 109     DWORD    dwRowsDone;      /* number of rows converted so far */
 110     BYTE     bThreshold;      /* white/black threshold; 0 -> diffuse */
 111     DWORD    dwInNextPos;     /* file pos for subsequent input */
 112     DWORD    dwOutNextPos;    /* file pos for subsequent output */
 113     DWORD    dwValidChk;      /* struct validity check value */
 114     short   *pErrBuf;         /* error-term buffer */
 115 } G2B_INST, *PG2B_INST;
 116
 117
 118
 119 /****************************************************************************\
 120  *
 121  * thresholdRow - work-horse thresholding routine
 122  *
 123 \****************************************************************************/
 124
 125 static void thresholdRow (
 126     int   iPixelsPerRow, /* in:  # of pixels in the row */
 127     BYTE  bThreshold,    /* in:  white/black threshold value */
 128     BYTE  baInBuf  [],   /* in:  input pixels (0=black, 255=white) */
 129     BYTE  baOutBuf [])   /* out: output pixels (0=white, 1=black, 8 per byte) */
 130 {
 131     int   iMore;
 132     PBYTE pbIn, pbOut;
 133     BYTE  bOut, bMask;
 134
 135     pbIn  = baInBuf;
 136     pbOut = baOutBuf;
 137
 138     for (iMore=iPixelsPerRow; iMore>0; iMore-=8)
 139     {
 140         bOut = 0;
 141
 142         for (bMask=0x80u; bMask!=0; bMask>>=1)
 143         {
 144             if (*pbIn++ < bThreshold)
 145                 bOut |= bMask;
 146         }
 147
 148         *pbOut++ = bOut;
 149     }
 150 }
 151
 152
 153
 154 /****************************************************************************\
 155  *
 156  * diffuseRow - work-horse error-diffusion routine
 157  *
 158 \****************************************************************************/
 159
 160 static void diffuseRow (
 161     int   iPixelsPerRow, /* in:  # of pixels in the row */
 162     short iaErrBuf [],   /* in/out: error-term buffer from prior call */
 163     BYTE  baInBuf  [],   /* in:  input pixels (0=black, 255=white) */
 164     BYTE  baOutBuf [])   /* out: output pixels (0=white, 1=black, 8 per byte) */
 165 {
 166     int     rr, r, cur;
 167     int     br, b, bl, bll;
 168     int     err;
 169     int     weight4, weight2, weight1;
 170     short   *eptr;
 171     int     noise;
 172     BYTE    *inptr, *inafter;
 173     BYTE    *outptr;
 174     BYTE    outvalue;
 175     int     mask;
 176     BOOL    second;   /* computing 2nd nibble in byte? */
 177
 178     /* The diffusion algorithm below uses the following 6 weights:
 179      *
 180      *         X 4 2
 181      *     1 3 4 2
 182      *
 183      * These weights add to 16, so there are shifts by 4 in the code.
 184      * weight4 is the 4 above.  Likewise with weight2 and weight1.
 185      * eptr is positioned at the 1 above.
 186      * The macro reads the error at the top 4 above, and writes it at the 1.
 187      * bll is positioned at the 1 above. bleft at the 3. below at the low 4.
 188      * The noise perturbations add to zero, so no net noise is injected.
 189      */
 190 #if 0
 191     #define DIFFUSE(par_outmask) {                                         \
 192         mask = cur >> (8*sizeof(cur)-1);   /* signed shift */              \
 193         outvalue |= par_outmask & mask;                                    \
 194         weight4 = (cur - (~mask&0x0ff0)) >> 2;                             \
 195                                                                            \
 196         noise = (cur & (0x7f<<1)) - 0x7f;                                  \
 197         cur     = ((unsigned)(*inptr++) << 4)                              \
 198                    + eptr[3] + weight2 + weight4  + noise    ;             \
 199         weight2    = (weight4>>1);                                         \
 200         weight1    = (weight2>>1);                                         \
 201         *eptr++ = bll        + weight1            - noise    ;             \
 202         bll     = bleft      + weight2 + weight1  /* + noise */ ;          \
 203         bleft   = below      + weight4            - noise    ;             \
 204         below   =              weight2            + noise    ;             \
 205     }
 206
 207     cur      = iaErrBuf[2] + ((unsigned)(*inptr++) << 4);
 208     bll      = 0;
 209     bleft    = 0;
 210     below    = 0;
 211     weight2  = 0;
 212
 213 #endif
 214
 215     #define DIFFUSE(par_outmask) {                                          \
 216         /* decide if output pixel is black or white */                      \
 217         mask = (cur-0x800) >> (8*sizeof(cur)-1); /* all 0's or all 1's */   \
 218         outvalue |= par_outmask & mask;                                     \
 219                                                                             \
 220         /* compute error, and weights of 4/16, 2/16 and 1/16 */             \
 221         err = cur - (~mask&0x0ff0);                                         \
 222         /* multiply error by 15/16 so it won't propagate a long distance */ \
 223         err = err - (err>>4);                                               \
 224         weight4 = err >> 2;                                                 \
 225         weight2 = weight4 >> 1;                                             \
 226         weight1 = weight2 >> 1;                                             \
 227                                                                             \
 228         /* distribute error to neighboring pixels */                        \
 229         noise = err & 0x00ff;                                               \
 230         rr  += weight2;                                                     \
 231         r   += weight4 + noise;                                             \
 232         br   = weight2 + noise;                                             \
 233         b   += weight4 - noise;                                             \
 234         bl  += weight2 + weight1;   /* the 3 weight */                      \
 235         bll += weight1 - noise;                                             \
 236                                                                             \
 237         /* advance right one pixel, so move values left one pixel */        \
 238         cur      = r;                                                       \
 239         r        = rr;                                                      \
 240         rr       = ((unsigned)(*inptr++) << 4) + eptr[2];                   \
 241         eptr[-2] = bll;                                                     \
 242         bll      = bl;                                                      \
 243         bl       = b;                                                       \
 244         b        = br;                                                      \
 245         eptr += 1;                                                          \
 246     }
 247
 248     inptr    = baInBuf;
 249     inafter  = baInBuf + iPixelsPerRow;
 250     outptr   = baOutBuf;
 251     eptr     = iaErrBuf + 2;
 252     outvalue = 0;
 253     second   = FALSE;
 254
 255     cur = ((unsigned)inptr[0] << 4) + eptr[0];
 256     r   = ((unsigned)inptr[1] << 4) + eptr[1];
 257     rr  = ((unsigned)inptr[2] << 4) + eptr[2];
 258     inptr += 3;
 259     bll = bl = b = br = 0;
 260
 261     while (inptr < inafter) {
 262         DIFFUSE (0x08);
 263         DIFFUSE (0x04);
 264         DIFFUSE (0x02);
 265         DIFFUSE (0x01);
 266
 267         if (! second) {
 268             /* we just computed the left half of the byte */
 269             outvalue <<= 4;
 270             second = TRUE;
 271         } else {
 272             /* we just computed the right half of the byte, so store it */
 273             *outptr++ = outvalue;
 274             outvalue = 0;
 275             second = FALSE;
 276         }
 277     } /* end of for */
 278
 279     if (second)
 280         *outptr = outvalue;    /* store final nibble */
 281
 282     eptr[-2] = bll;
 283     eptr[-1] = bl;
 284     eptr[ 0] = b;
 285
 286     #undef DIFFUSE
 287 }
 288
 289
 290
 291 /*****************************************************************************\
 292  *
 293  * gray2bi_openXform - Creates a new instance of the transformer
 294  *
 295  *****************************************************************************
 296  *
 297  * This returns a handle for the new instance to be passed into
 298  * all subsequent calls.
 299  *
 300  * Return value: IP_DONE=success; IP_FATAL_ERROR=misc error.
 301  *
 302 \*****************************************************************************/
 303
 304 static WORD gray2bi_openXform (
 305     IP_XFORM_HANDLE *pXform)   /* out: returned handle */
 306 {
 307     PG2B_INST g;
 308
 309     INSURE (pXform != NULL);
 310     IP_MEM_ALLOC (sizeof(G2B_INST), g);
 311     *pXform = g;
 312     memset (g, 0, sizeof(G2B_INST));
 313     g->dwValidChk = CHECK_VALUE;
 314     return IP_DONE;
 315
 316     fatal_error:
 317     return IP_FATAL_ERROR;
 318 }
 319
 320
 321
 322 /*****************************************************************************\
 323  *
 324  * gray2bi_setDefaultInputTraits - Specifies default input image traits
 325  *
 326  *****************************************************************************
 327  *
 328  * The header of the file-type handled by the transform probably does
 329  * not include *all* the image traits we'd like to know.  Those not
 330  * specified in the file-header are filled in from info provided by
 331  * this routine.
 332  *
 333  * Return value: IP_DONE=success; IP_FATAL_ERROR=misc error.
 334  *
 335 \*****************************************************************************/
 336
 337 static WORD gray2bi_setDefaultInputTraits (
 338     IP_XFORM_HANDLE  hXform,     /* in: handle for xform */
 339     PIP_IMAGE_TRAITS pTraits)    /* in: default image traits */
 340 {
 341     PG2B_INST g;
 342
 343     HANDLE_TO_PTR (hXform, g);
 344
 345     /* Insure that values we care about are correct */
 346     INSURE (pTraits->iBitsPerPixel == 8);
 347     INSURE (pTraits->iComponentsPerPixel == 1);
 348     INSURE (pTraits->iPixelsPerRow > 0);
 349
 350     g->inTraits = *pTraits;   /* a structure copy */
 351
 352     return IP_DONE;
 353
 354     fatal_error:
 355     return IP_FATAL_ERROR;
 356 }
 357
 358
 359
 360 /*****************************************************************************\
 361  *
 362  * gray2bi_setXformSpec - Provides xform-specific information
 363  *
 364 \*****************************************************************************/
 365
 366 static WORD gray2bi_setXformSpec (
 367     IP_XFORM_HANDLE hXform,         /* in: handle for xform */
 368     DWORD_OR_PVOID  aXformInfo[])   /* in: xform information */
 369 {
 370     PG2B_INST g;
 371
 372     HANDLE_TO_PTR (hXform, g);
 373     INSURE ((DWORD)aXformInfo[IP_GRAY_2_BI_THRESHOLD].dword <= 255);
 374     g->bThreshold = (BYTE)aXformInfo[IP_GRAY_2_BI_THRESHOLD].dword;
 375
 376     return IP_DONE;
 377
 378     fatal_error:
 379     return IP_FATAL_ERROR;
 380 }
 381
 382
 383
 384 /*****************************************************************************\
 385  *
 386  * gray2bi_getHeaderBufSize- Returns size of input buf needed to hold header
 387  *
 388 \*****************************************************************************/
 389
 390 static WORD gray2bi_getHeaderBufSize (
 391     IP_XFORM_HANDLE  hXform,         /* in:  handle for xform */
 392     DWORD           *pdwInBufLen)    /* out: buf size for parsing header */
 393 {
 394     /* since input is raw pixels, there is no header, so set it to zero */
 395     *pdwInBufLen = 0;
 396     return IP_DONE;
 397 }
 398
 399
 400
 401 /*****************************************************************************\
 402  *
 403  * gray2bi_getActualTraits - Parses header, and returns input & output traits
 404  *
 405 \*****************************************************************************/
 406
 407 static WORD gray2bi_getActualTraits (
 408     IP_XFORM_HANDLE  hXform,         /* in:  handle for xform */
 409     DWORD            dwInputAvail,   /* in:  # avail bytes in input buf */
 410     PBYTE            pbInputBuf,     /* in:  ptr to input buffer */
 411     PDWORD           pdwInputUsed,   /* out: # bytes used from input buf */
 412     PDWORD           pdwInputNextPos,/* out: file-pos to read from next */
 413     PIP_IMAGE_TRAITS pInTraits,      /* out: input image traits */
 414     PIP_IMAGE_TRAITS pOutTraits)     /* out: output image traits */
 415 {
 416     PG2B_INST g;
 417     int       nBytes;
 418
 419     HANDLE_TO_PTR (hXform, g);
 420
 421     /* Since there is no header, we'll report no usage of input */
 422     *pdwInputUsed    = 0;
 423     *pdwInputNextPos = 0;
 424
 425     *pInTraits  = g->inTraits;
 426     *pOutTraits = g->inTraits;
 427     pOutTraits->iBitsPerPixel = 1; /* this xform only changes bits/pixel */
 428
 429     if (g->bThreshold == 0) {
 430         nBytes = sizeof(short) * g->inTraits.iPixelsPerRow;
 431         IP_MEM_ALLOC (nBytes, g->pErrBuf);
 432         memset (g->pErrBuf, 0, nBytes);
 433     }
 434
 435     return IP_DONE | IP_READY_FOR_DATA;
 436
 437     fatal_error:
 438     return IP_FATAL_ERROR;
 439 }
 440
 441
 442
 443 /****************************************************************************\
 444  *
 445  * gray2bi_getActualBufSizes - Returns buf sizes needed for remainder of job
 446  *
 447 \****************************************************************************/
 448
 449 static WORD gray2bi_getActualBufSizes (
 450     IP_XFORM_HANDLE hXform,          /* in:  handle for xform */
 451     PDWORD          pdwMinInBufLen,  /* out: min input buf size */
 452     PDWORD          pdwMinOutBufLen) /* out: min output buf size */
 453 {
 454     PG2B_INST g;
 455
 456     HANDLE_TO_PTR (hXform, g);
 457     *pdwMinInBufLen  =  g->inTraits.iPixelsPerRow;
 458     *pdwMinOutBufLen = (g->inTraits.iPixelsPerRow + 7) / 8;
 459
 460     return IP_DONE;
 461
 462     fatal_error:
 463     return IP_FATAL_ERROR;
 464 }
 465
 466
 467
 468 /*****************************************************************************\
 469  *
 470  * gray2bi_convert - error-diffuses one row
 471  *
 472 \*****************************************************************************/
 473
 474 static WORD gray2bi_convert (
 475     IP_XFORM_HANDLE hXform,
 476     DWORD           dwInputAvail,     /* in:  # avail bytes in in-buf */
 477     PBYTE           pbInputBuf,       /* in:  ptr to in-buffer */
 478     PDWORD          pdwInputUsed,     /* out: # bytes used from in-buf */
 479     PDWORD          pdwInputNextPos,  /* out: file-pos to read from next */
 480     DWORD           dwOutputAvail,    /* in:  # avail bytes in out-buf */
 481     PBYTE           pbOutputBuf,      /* in:  ptr to out-buffer */
 482     PDWORD          pdwOutputUsed,    /* out: # bytes written in out-buf */
 483     PDWORD          pdwOutputThisPos) /* out: file-pos to write the data */
 484 {
 485     PG2B_INST g;
 486     int       inBytes, outBytes;
 487
 488     HANDLE_TO_PTR (hXform, g);
 489
 490     /**** Check if we were told to flush ****/
 491
 492     if (pbInputBuf == NULL) {
 493         PRINT (_T("gray2bi_convert: Told to flush.\n"), 0, 0);
 494         *pdwInputUsed = *pdwOutputUsed = 0;
 495         *pdwInputNextPos  = g->dwInNextPos;
 496         *pdwOutputThisPos = g->dwOutNextPos;
 497         return IP_DONE;
 498     }
 499
 500     /**** Convert and Output a Row ****/
 501
 502     inBytes  = g->inTraits.iPixelsPerRow;
 503     outBytes = (inBytes + 7) / 8;
 504     INSURE (dwInputAvail  >= (DWORD)inBytes );
 505     INSURE (dwOutputAvail >= (DWORD)outBytes);
 506
 507     if (g->bThreshold == 0) {
 508         INSURE (g->pErrBuf != NULL);
 509         diffuseRow (inBytes, g->pErrBuf, pbInputBuf, pbOutputBuf);
 510     } else
 511         thresholdRow (inBytes, g->bThreshold, pbInputBuf, pbOutputBuf);
 512
 513     *pdwInputUsed     = inBytes;
 514     g->dwInNextPos   += inBytes;
 515     *pdwInputNextPos  = g->dwInNextPos;
 516
 517     *pdwOutputUsed    = outBytes;
 518     *pdwOutputThisPos = g->dwOutNextPos;
 519     g->dwOutNextPos  += outBytes;
 520
 521     g->dwRowsDone += 1;
 522
 523     return IP_CONSUMED_ROW | IP_PRODUCED_ROW | IP_READY_FOR_DATA;
 524
 525     fatal_error:
 526     return IP_FATAL_ERROR;
 527 }
 528
 529
 530
 531 /*****************************************************************************\
 532  *
 533  * gray2bi_insertedData - client inserted into our output stream
 534  *
 535 \*****************************************************************************/
 536
 537 static WORD gray2bi_insertedData (
 538     IP_XFORM_HANDLE hXform,
 539     DWORD           dwNumBytes)
 540 {
 541     fatalBreakPoint ();
 542     return IP_FATAL_ERROR;   /* must never be called (can't insert data) */
 543 }
 544
 545
 546
 547 /*****************************************************************************\
 548  *
 549  * gray2bi_newPage - Tells us to flush this page, and start a new page
 550  *
 551 \*****************************************************************************/
 552
 553 static WORD gray2bi_newPage (
 554     IP_XFORM_HANDLE hXform)
 555 {
 556     PG2B_INST g;
 557
 558     HANDLE_TO_PTR (hXform, g);
 559     /* todo: return fatal error if convert is called again? */
 560     return IP_DONE;   /* can't insert page-breaks, so ignore this call */
 561
 562     fatal_error:
 563     return IP_FATAL_ERROR;
 564
 565 }
 566
 567
 568
 569 /*****************************************************************************\
 570  *
 571  * gray2bi_closeXform - Destroys this instance
 572  *
 573 \*****************************************************************************/
 574
 575 static WORD gray2bi_closeXform (IP_XFORM_HANDLE hXform)
 576 {
 577     PG2B_INST g;
 578
 579     HANDLE_TO_PTR (hXform, g);
 580
 581     if (g->pErrBuf != NULL)
 582         IP_MEM_FREE (g->pErrBuf);
 583
 584     g->dwValidChk = 0;
 585     IP_MEM_FREE (g);       /* free memory for the instance */
 586
 587     return IP_DONE;
 588
 589     fatal_error:
 590     return IP_FATAL_ERROR;
 591 }
 592
 593
 594
 595 /*****************************************************************************\
 596  *
 597  * gray2biTbl - Jump-table for encoder
 598  *
 599 \*****************************************************************************/
 600
 601 IP_XFORM_TBL gray2biTbl = {
 602     gray2bi_openXform,
 603     gray2bi_setDefaultInputTraits,
 604     gray2bi_setXformSpec,
 605     gray2bi_getHeaderBufSize,
 606     gray2bi_getActualTraits,
 607     gray2bi_getActualBufSizes,
 608     gray2bi_convert,
 609     gray2bi_newPage,
 610     gray2bi_insertedData,
 611     gray2bi_closeXform
 612 };
 613
 614 /* End of File */