Logo Search packages:      
Sourcecode: leptonlib version File versions  Download package

bbuffer.c

/*====================================================================*
 -  Copyright (C) 2001 Leptonica.  All rights reserved.
 -  This software is distributed in the hope that it will be
 -  useful, but with NO WARRANTY OF ANY KIND.
 -  No author or distributor accepts responsibility to anyone for the
 -  consequences of using this software, or for whether it serves any
 -  particular purpose or works at all, unless he or she says so in
 -  writing.  Everyone is granted permission to copy, modify and
 -  redistribute this source code, for commercial or non-commercial
 -  purposes, with the following restrictions: (1) the origin of this
 -  source code must not be misrepresented; (2) modified versions must
 -  be plainly marked as such; and (3) this notice may not be removed
 -  or altered from any source or modified source distribution.
 *====================================================================*/


/*
 *   bbuffer.c
 *
 *      Create/Destroy BBuffer
 *          BBUFFER   *bbufferCreate()
 *          void      *bbufferDestroy()
 *          l_uint8   *bbufferDestroyAndSaveData()
 *
 *      Operations to read data TO a BBuffer
 *          l_int32    bbufferRead()
 *          l_int32    bbufferReadStream()
 *          l_int32    bbufferExtendArray()
 *
 *      Operations to write data FROM a BBuffer
 *          l_int32    bbufferWrite()
 *          l_int32    bbufferWriteStream()
 *
 *      Accessors
 *          l_int32    bbufferBytesToWrite()
 *
 *      Example application
 *          l_uint8   *zlibCompress()
 *          l_uint8   *zlibUncompress()
 *
 *
 *    The bbuffer is an implementation of a byte queue.
 *    The bbuffer holds a byte array from which bytes are
 *    processed in a first-in/first-out fashion.  As with
 *    any queue, bbuffer maintains two "pointers," one to the
 *    tail of the queue (where you read new bytes onto it)
 *    and one to the head of the queue (where you start from
 *    when writing bytes out of it. 
 *
 *    The queue can be visualized:
 *
 *      
 *  byte 0                                           byte (nalloc - 1)
 *       |                                                |
 *       --------------------------------------------------
 *                 H                             T
 *       [   aw   ][  bytes currently on queue  ][  anr   ] 
 *    
 *       ---:  all allocated data in bbuffer
 *       H:    queue head (ptr to next byte to be written out)
 *       T:    queue tail (ptr to first byte to be written to) 
 *       aw:   already written from queue
 *       anr:  allocated but not yet read to
 *
 *    The purpose of bbuffer is to allow you to safely read
 *    bytes in, and to sequentially write them out as well.
 *    In the process of writing bytes out, you don't actually
 *    remove the bytes in the array; you just move the pointer
 *    (nwritten) which points to the head of the queue.  In
 *    the process of reading bytes in, you sometimes need to
 *    expand the array size.  If a read is performed after a
 *    write, so that the head of the queue is not at the
 *    beginning of the array, the bytes already written are
 *    first removed by copying the others over them; then the
 *    new bytes are read onto the tail of the queue.
 *
 *    Note that the meaning of "read into" and "write from"
 *    the bbuffer is OPPOSITE to that for a stream, where
 *    you read "from" a stream and write "into" a stream.
 *    As a mnemonic for remembering the direction:
 *        - to read bytes from a stream into the bbuffer,
 *          you call fread on the stream
 *        - to write bytes from the bbuffer into a stream,
 *          you call fwrite on the stream
 *
 *    For an example use, we use zlib to compress and decompress
 *    a byte array from one memory buffer to another.  The
 *    standard method uses streams, and we use the bbuffer
 *    as an expandable queue of pixels for both the reading
 *    and writing side.  With memory mapping, one should be
 *    able to compress between memory buffers by using the
 *    file system to buffer everything in the background.
 *    But the bbuffer implementation is more portable.
 */

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <zlib.h>
#include "allheaders.h"

static const l_int32  INITIAL_BUFFER_ARRAYSIZE = 1024;   /* n'importe quoi */

    /* for zlibCompress() and zlibUncompress() */
static const l_int32  BUFSIZE = 32768;
static const l_int32  ZLIB_COMPRESSION_LEVEL = 6;



/*--------------------------------------------------------------------------*
 *                         BBuffer create/destroy                           *
 *--------------------------------------------------------------------------*/
/*!
 *  bbufferCreate()
 *
 *      Input:  buffer address in memory (<optional>)
 *              size of byte array to be alloc'd (0 for default)
 *      Return: bbuffer, or null on error
 *
 *  Action: allocates a bbuffer with associated byte array of
 *          the given size.  If a buffer address is given,
 *          it then reads the number of bytes into the byte array.
 *  Note: If a buffer address is given, you should read all the data in.
 */
BBUFFER *
bbufferCreate(l_uint8  *indata,
              l_int32   nalloc)
{
BBUFFER  *bb;

    PROCNAME("bbufferCreate");

    if (nalloc <= 0)
      nalloc = INITIAL_BUFFER_ARRAYSIZE;

    if ((bb = (BBUFFER *)CALLOC(1, sizeof(BBUFFER))) == NULL)
        return (BBUFFER *)ERROR_PTR("bb not made", procName, NULL);
    if ((bb->array = (l_uint8 *)CALLOC(nalloc, sizeof(l_uint8))) == NULL)
        return (BBUFFER *)ERROR_PTR("byte array not made", procName, NULL);
    bb->nalloc = nalloc;
    bb->nwritten = 0;

    if (indata) {
      memcpy((l_uint8 *)bb->array, indata, nalloc);
      bb->n = nalloc;
    }
    else
      bb->n = 0;

    return bb;
}


/*!
 *  bbufferDestroy()
 *
 *      Input:  &bbuffer  (<to be nulled>)
 *      Return: void
 *
 *  Action: destroys the byte array in the bbuffer and then the bbuffer;
 *          then nulls the contents of the input ptr.
 */
void
bbufferDestroy(BBUFFER  **pbb)
{
BBUFFER  *bb;

    PROCNAME("bbufferDestroy");

    if (pbb == NULL) {
      L_WARNING("ptr address is NULL", procName);
      return;
    }

    if ((bb = *pbb) == NULL)
      return;

    if (bb->array)
      FREE((void *)bb->array);
    FREE((void *)bb);
    *pbb = NULL;

    return;
}


/*!
 *  bbufferDestroyAndSaveData()
 *
 *      Input:  &bbuffer (<to be nulled>)
 *              &nbytes  (<return> number of bytes saved in array)
 *      Return: barray (newly allocated array of data)
 *
 *  Action: copies data to newly allocated array; then destroys the bbuffer.
 */
l_uint8 *
bbufferDestroyAndSaveData(BBUFFER  **pbb,
                          l_int32   *pnbytes)
{
l_uint8  *array;
l_int32   nbytes;
BBUFFER  *bb;

    PROCNAME("bbufferDestroyAndSaveData");

    if (pbb == NULL) {
      L_WARNING("ptr address is NULL", procName);
      return NULL;
    }
    if (pnbytes == NULL) {
      L_WARNING("&nbytes is NULL", procName);
      bbufferDestroy(pbb);
      return NULL;
    }

    if ((bb = *pbb) == NULL)
      return NULL;

      /* write all unwritten bytes out to a new array */
    nbytes = bb->n - bb->nwritten;
    *pnbytes = nbytes;
    if ((array = (l_uint8 *)CALLOC(nbytes, sizeof(l_uint8))) == NULL) {
      L_WARNING("calloc failure for array", procName);
      return NULL;
    }
    memcpy((void *)array, (void *)(bb->array + bb->nwritten), nbytes);

    bbufferDestroy(pbb);
    return array;
}


        
/*--------------------------------------------------------------------------*
 *                   Operations to read data INTO a BBuffer                 *
 *--------------------------------------------------------------------------*/
/*!
 *  bbufferRead()
 *
 *      Input:  bbuffer
 *              src      (source memory buffer from which bytes are read)
 *              nbytes   (bytes to be read)
 *      Return: 0 if OK, 1 on error
 *
 *  Note: For a read after write, we first remove the written
 *        bytes by shifting the unwritten bytes in the array,
 *        then check if there is enough room to add the new bytes.
 *        If not, we realloc with bbufferExpandArray(), resulting
 *        in a second writing of the unwritten bytes.  While less
 *        efficient, this is simpler than making a special case
 *        of reallocNew().
 */
l_int32
bbufferRead(BBUFFER  *bb,
            l_uint8  *src,
          l_int32   nbytes)
{
l_int32  navail, nadd, nwritten;

    PROCNAME("bbufferRead");

    if (!bb)
        return ERROR_INT("bb not defined", procName, 1);
    if (!src)
        return ERROR_INT("src not defined", procName, 1);
    if (nbytes == 0)
        return ERROR_INT("no bytes to read", procName, 1);
    
    if ((nwritten = bb->nwritten)) {  /* move the unwritten bytes over */
      memmove((l_uint8 *)bb->array, (l_uint8 *)(bb->array + nwritten),
               bb->n - nwritten);
      bb->nwritten = 0;
      bb->n -= nwritten;
    }

      /* If necessary, expand the allocated array.  Do so by
       * by at least a factor of two. */
    navail = bb->nalloc - bb->n;
    if (nbytes > navail) {
        nadd = L_MAX(bb->nalloc, nbytes);
      bbufferExtendArray(bb, nadd);
    }

      /* Read in the new bytes */
    memcpy((l_uint8 *)(bb->array + bb->n), src, nbytes);
    bb->n += nbytes;

    return 0;
}


/*!
 *  bbufferReadStream()
 *
 *      Input:  bbuffer
 *              fp      (source stream from which bytes are read)
 *              nbytes   (bytes to be read)
 *      Return: 0 if OK, 1 on error
 */
l_int32
bbufferReadStream(BBUFFER  *bb,
                  FILE     *fp,
                l_int32   nbytes)
{
l_int32  navail, nadd, nread, nwritten;

    PROCNAME("bbufferReadStream");

    if (!bb)
        return ERROR_INT("bb not defined", procName, 1);
    if (!fp)
        return ERROR_INT("fp not defined", procName, 1);
    if (nbytes == 0)
        return ERROR_INT("no bytes to read", procName, 1);
    
    if ((nwritten = bb->nwritten)) {  /* move any unwritten bytes over */
      memmove((l_uint8 *)bb->array, (l_uint8 *)(bb->array + nwritten),
               bb->n - nwritten);
      bb->nwritten = 0;
      bb->n -= nwritten;
    }

      /* If necessary, expand the allocated array.  Do so by
       * by at least a factor of two. */
    navail = bb->nalloc - bb->n;
    if (nbytes > navail) {
        nadd = L_MAX(bb->nalloc, nbytes);
      bbufferExtendArray(bb, nadd);
    }

      /* Read in the new bytes */
    nread = fread((void *)(bb->array + bb->n), 1, nbytes, fp);
    bb->n += nread;

    return 0;
}


/*!
 *  bbufferExtendArray()
 *
 *      Input:  bbuffer
 *              nbytes  (number of bytes to extend array size)
 *      Return: 0 if OK, 1 on error
 *
 *  Note: reallocNew() copies all bb->nalloc bytes, even though
 *        only bb->n are data.
 */
l_int32
bbufferExtendArray(BBUFFER  *bb,
                   l_int32   nbytes)
{
    PROCNAME("bbufferExtendArray");

    if (!bb)
        return ERROR_INT("bb not defined", procName, 1);

    if ((bb->array = (l_uint8 *)reallocNew((void **)&bb->array,
                        bb->nalloc,
                        bb->nalloc + nbytes)) == NULL)
          return ERROR_INT("new ptr array not returned", procName, 1);

    bb->nalloc += nbytes;
    return 0;
}



/*--------------------------------------------------------------------------*
 *                  Operations to write data FROM a BBuffer                 *
 *--------------------------------------------------------------------------*/
/*!
 *  bbufferWrite()
 *
 *      Input:  bbuffer
 *              dest     (dest memory buffer to which bytes are written)
 *              nbytes   (bytes requested to be written)
 *              &nout    (<return> bytes actually written)
 *      Return: 0 if OK, 1 on error
 */
l_int32
bbufferWrite(BBUFFER  *bb,
             l_uint8  *dest,
           l_int32   nbytes,
           l_int32  *pnout)
{
l_int32  nleft, nout;

    PROCNAME("bbufferWrite");

    if (!bb)
        return ERROR_INT("bb not defined", procName, 1);
    if (!dest)
        return ERROR_INT("dest not defined", procName, 1);
    if (nbytes <= 0)
        return ERROR_INT("no bytes requested to write", procName, 1);
    if (!pnout)
        return ERROR_INT("&nout not defined", procName, 1);
    
    nleft = bb->n - bb->nwritten;
    nout = L_MIN(nleft, nbytes);
    *pnout = nout;

    if (nleft == 0) {   /* nothing to write; reinitialize the buffer */
      bb->n = 0;
      bb->nwritten = 0;
      return 0;
    }

      /* nout > 0; transfer the data out */
    memcpy(dest, (l_uint8 *)(bb->array + bb->nwritten), nout);
    bb->nwritten += nout;

      /* if all written; "empty" the buffer */
    if (nout == nleft) { 
      bb->n = 0;
      bb->nwritten = 0;
    }

    return 0;
}


/*!
 *  bbufferWriteStream()
 *
 *      Input:  bbuffer
 *              fp       (dest stream to which bytes are written)
 *              nbytes   (bytes requested to be written)
 *              &nout    (<return> bytes actually written)
 *      Return: 0 if OK, 1 on error
 */
l_int32
bbufferWriteStream(BBUFFER  *bb,
                   FILE     *fp,
                 l_int32   nbytes,
                 l_int32  *pnout)
{
l_int32  nleft, nout;

    PROCNAME("bbufferWriteStream");

    if (!bb)
        return ERROR_INT("bb not defined", procName, 1);
    if (!fp)
        return ERROR_INT("output stream not defined", procName, 1);
    if (nbytes <= 0)
        return ERROR_INT("no bytes requested to write", procName, 1);
    if (!pnout)
        return ERROR_INT("&nout not defined", procName, 1);
    
    nleft = bb->n - bb->nwritten;
    nout = L_MIN(nleft, nbytes);
    *pnout = nout;

    if (nleft == 0) {   /* nothing to write; reinitialize the buffer */
      bb->n = 0;
      bb->nwritten = 0;
      return 0;
    }

      /* nout > 0; transfer the data out */
    fwrite((void *)(bb->array + bb->nwritten), 1, nout, fp);
    bb->nwritten += nout;

      /* if all written; "empty" the buffer */
    if (nout == nleft) { 
      bb->n = 0;
      bb->nwritten = 0;
    }

    return 0;
}



/*--------------------------------------------------------------------------*
 *                                  Accessors                               *
 *--------------------------------------------------------------------------*/
/*!
 *  bbufferBytesToWrite()
 *
 *      Input:  bbuffer
 *              &nbytes (<return>)
 *      Return: 0 if OK; 1 on error
 */
l_int32
bbufferBytesToWrite(BBUFFER  *bb,
                    l_int32  *pnbytes)
{

    PROCNAME("bbufferBytesToWrite");

    if (!bb)
        return ERROR_INT("bb not defined", procName, 1);
    if (!pnbytes)
        return ERROR_INT("&nbytes not defined", procName, 1);

    *pnbytes = bb->n - bb->nwritten;
    return 0;
}
      

/*--------------------------------------------------------------------------*
 *                           Zlib example application                       *
 *--------------------------------------------------------------------------*/
/*!
 *  zlibCompress()
 *
 *      Input:  datain (byte buffer with input data)
 *              nin    (number of bytes of input data)
 *              &nout  (<return> number of bytes of output data)
 *      Return: dataout (compressed data), or null on error
 *
 *  Note: We repeatedly read in and fill up an input buffer,
 *        compress the data, and read it back out.  zlib
 *        uses two byte buffers internally in the z_stream
 *        data structure.  We use the bbuffers to feed data
 *        into the fixed bufferin, and feed it out of bufferout,
 *        in the same way that a pair of streams would normally
 *        be used if the data were being read from one file
 *        and written to another.  This is done iteratively,
 *        compressing BUFSIZE bytes of input data at a time.
 */
l_uint8 *
zlibCompress(l_uint8  *datain,
             l_int32   nin,
           l_int32  *pnout)
{
l_uint8  *dataout;
l_int32   status, nbytes;
l_uint8  *bufferin, *bufferout;
BBUFFER  *bbin, *bbout;
z_stream  z;

    PROCNAME("zlibCompress");

    if (!datain)
      return (l_uint8 *)ERROR_PTR("datain not defined", procName, NULL);

      /* set up fixed size buffers used in z_stream */
    if ((bufferin = (l_uint8 *)CALLOC(BUFSIZE, sizeof(l_uint8))) == NULL)
      return (l_uint8 *)ERROR_PTR("bufferin not made", procName, NULL);
    if ((bufferout = (l_uint8 *)CALLOC(BUFSIZE, sizeof(l_uint8))) == NULL)
      return (l_uint8 *)ERROR_PTR("bufferout not made", procName, NULL);

      /* set up bbuffers and load bbin with the data */
    if ((bbin = bbufferCreate(datain, nin)) == NULL)
      return (l_uint8 *)ERROR_PTR("bbin not made", procName, NULL);
    if ((bbout = bbufferCreate(NULL, 0)) == NULL)
      return (l_uint8 *)ERROR_PTR("bbout not made", procName, NULL);

    z.zalloc = (alloc_func)0;
    z.zfree = (free_func)0;
    z.opaque = (voidpf)0;

    z.next_in = bufferin;
    z.avail_in = 0;
    z.next_out = bufferout;
    z.avail_out = BUFSIZE;

    deflateInit(&z, ZLIB_COMPRESSION_LEVEL);

    for ( ; ; ) {
      if (z.avail_in == 0) {
          z.next_in = bufferin;
          bbufferWrite(bbin, bufferin, BUFSIZE, &nbytes);
/*        fprintf(stderr, " wrote %d bytes to bufferin\n", nbytes); */
          z.avail_in = nbytes;
      }
      if (z.avail_in == 0)
          break;
      status = deflate(&z, Z_SYNC_FLUSH);
/*    fprintf(stderr, " status is %d, bytesleft = %d, totalout = %d\n",
                status, z.avail_out, z.total_out); */
      nbytes = BUFSIZE - z.avail_out;
      if (nbytes) {
          bbufferRead(bbout, bufferout, nbytes);
/*        fprintf(stderr, " read %d bytes from bufferout\n", nbytes); */
      }
      z.next_out = bufferout;
      z.avail_out = BUFSIZE;
    }

    deflateEnd(&z);

    bbufferDestroy(&bbin);
    dataout = bbufferDestroyAndSaveData(&bbout, pnout);

    FREE((void *)bufferin);
    FREE((void *)bufferout);
    return dataout;
}
      

/*!
 *  zlibUncompress()
 *
 *      Input:  datain (byte buffer with compressed input data)
 *              nin    (number of bytes of input data)
 *              &nout  (<return> number of bytes of output data)
 *      Return: dataout (uncompressed data), or null on error
 *
 *  Note: see comments in zlibCompress()
 */
l_uint8 *
zlibUncompress(l_uint8  *datain,
               l_int32   nin,
             l_int32  *pnout)
{
l_uint8  *dataout;
l_int32   status, nbytes;
l_uint8  *bufferin, *bufferout;
BBUFFER  *bbin, *bbout;
z_stream  z;

    PROCNAME("zlibUncompress");

    if (!datain)
      return (l_uint8 *)ERROR_PTR("datain not defined", procName, NULL);
    
    if ((bufferin = (l_uint8 *)CALLOC(BUFSIZE, sizeof(l_uint8))) == NULL)
      return (l_uint8 *)ERROR_PTR("bufferin not made", procName, NULL);
    if ((bufferout = (l_uint8 *)CALLOC(BUFSIZE, sizeof(l_uint8))) == NULL)
      return (l_uint8 *)ERROR_PTR("bufferout not made", procName, NULL);

    if ((bbin = bbufferCreate(datain, nin)) == NULL)
      return (l_uint8 *)ERROR_PTR("bbin not made", procName, NULL);
    if ((bbout = bbufferCreate(NULL, 0)) == NULL)
      return (l_uint8 *)ERROR_PTR("bbout not made", procName, NULL);

    z.zalloc = (alloc_func)0;
    z.zfree = (free_func)0;

    z.next_in = bufferin;
    z.avail_in = 0;
    z.next_out = bufferout;
    z.avail_out = BUFSIZE;

    inflateInit(&z);

    for ( ; ; ) {
      if (z.avail_in == 0) {
          z.next_in = bufferin;
          bbufferWrite(bbin, bufferin, BUFSIZE, &nbytes);
/*        fprintf(stderr, " wrote %d bytes to bufferin\n", nbytes); */
          z.avail_in = nbytes;
      }
      if (z.avail_in == 0)
          break;
      status = inflate(&z, Z_SYNC_FLUSH);
/*    fprintf(stderr, " status is %d, bytesleft = %d, totalout = %d\n",
                status, z.avail_out, z.total_out); */
      nbytes = BUFSIZE - z.avail_out;
      if (nbytes) {
          bbufferRead(bbout, bufferout, nbytes);
/*        fprintf(stderr, " read %d bytes from bufferout\n", nbytes); */
      }
      z.next_out = bufferout;
      z.avail_out = BUFSIZE;
    }

    inflateEnd(&z);

    bbufferDestroy(&bbin);
    dataout = bbufferDestroyAndSaveData(&bbout, pnout);

    FREE((void *)bufferin);
    FREE((void *)bufferout);
    return dataout;
}


Generated by  Doxygen 1.6.0   Back to index