Blame libdjvu/JB2Image.h

Packit df99a1
//C-  -*- C++ -*-
Packit df99a1
//C- -------------------------------------------------------------------
Packit df99a1
//C- DjVuLibre-3.5
Packit df99a1
//C- Copyright (c) 2002  Leon Bottou and Yann Le Cun.
Packit df99a1
//C- Copyright (c) 2001  AT&T
Packit df99a1
//C-
Packit df99a1
//C- This software is subject to, and may be distributed under, the
Packit df99a1
//C- GNU General Public License, either Version 2 of the license,
Packit df99a1
//C- or (at your option) any later version. The license should have
Packit df99a1
//C- accompanied the software or you may obtain a copy of the license
Packit df99a1
//C- from the Free Software Foundation at http://www.fsf.org .
Packit df99a1
//C-
Packit df99a1
//C- This program is distributed in the hope that it will be useful,
Packit df99a1
//C- but WITHOUT ANY WARRANTY; without even the implied warranty of
Packit df99a1
//C- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
Packit df99a1
//C- GNU General Public License for more details.
Packit df99a1
//C- 
Packit df99a1
//C- DjVuLibre-3.5 is derived from the DjVu(r) Reference Library from
Packit df99a1
//C- Lizardtech Software.  Lizardtech Software has authorized us to
Packit df99a1
//C- replace the original DjVu(r) Reference Library notice by the following
Packit df99a1
//C- text (see doc/lizard2002.djvu and doc/lizardtech2007.djvu):
Packit df99a1
//C-
Packit df99a1
//C-  ------------------------------------------------------------------
Packit df99a1
//C- | DjVu (r) Reference Library (v. 3.5)
Packit df99a1
//C- | Copyright (c) 1999-2001 LizardTech, Inc. All Rights Reserved.
Packit df99a1
//C- | The DjVu Reference Library is protected by U.S. Pat. No.
Packit df99a1
//C- | 6,058,214 and patents pending.
Packit df99a1
//C- |
Packit df99a1
//C- | This software is subject to, and may be distributed under, the
Packit df99a1
//C- | GNU General Public License, either Version 2 of the license,
Packit df99a1
//C- | or (at your option) any later version. The license should have
Packit df99a1
//C- | accompanied the software or you may obtain a copy of the license
Packit df99a1
//C- | from the Free Software Foundation at http://www.fsf.org .
Packit df99a1
//C- |
Packit df99a1
//C- | The computer code originally released by LizardTech under this
Packit df99a1
//C- | license and unmodified by other parties is deemed "the LIZARDTECH
Packit df99a1
//C- | ORIGINAL CODE."  Subject to any third party intellectual property
Packit df99a1
//C- | claims, LizardTech grants recipient a worldwide, royalty-free, 
Packit df99a1
//C- | non-exclusive license to make, use, sell, or otherwise dispose of 
Packit df99a1
//C- | the LIZARDTECH ORIGINAL CODE or of programs derived from the 
Packit df99a1
//C- | LIZARDTECH ORIGINAL CODE in compliance with the terms of the GNU 
Packit df99a1
//C- | General Public License.   This grant only confers the right to 
Packit df99a1
//C- | infringe patent claims underlying the LIZARDTECH ORIGINAL CODE to 
Packit df99a1
//C- | the extent such infringement is reasonably necessary to enable 
Packit df99a1
//C- | recipient to make, have made, practice, sell, or otherwise dispose 
Packit df99a1
//C- | of the LIZARDTECH ORIGINAL CODE (or portions thereof) and not to 
Packit df99a1
//C- | any greater extent that may be necessary to utilize further 
Packit df99a1
//C- | modifications or combinations.
Packit df99a1
//C- |
Packit df99a1
//C- | The LIZARDTECH ORIGINAL CODE is provided "AS IS" WITHOUT WARRANTY
Packit df99a1
//C- | OF ANY KIND, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
Packit df99a1
//C- | TO ANY WARRANTY OF NON-INFRINGEMENT, OR ANY IMPLIED WARRANTY OF
Packit df99a1
//C- | MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Packit df99a1
//C- +------------------------------------------------------------------
Packit df99a1
Packit df99a1
#ifndef _JB2IMAGE_H
Packit df99a1
#define _JB2IMAGE_H
Packit df99a1
#ifdef HAVE_CONFIG_H
Packit df99a1
#include "config.h"
Packit df99a1
#endif
Packit df99a1
#if NEED_GNUG_PRAGMAS
Packit df99a1
# pragma interface
Packit df99a1
#endif
Packit df99a1
Packit df99a1
/** @name JB2Image.h
Packit df99a1
Packit df99a1
    Files #"JB2Image.h"# and #"JB2Image.cpp"# address the compression of
Packit df99a1
    bilevel images using the JB2 soft pattern matching scheme.  These files
Packit df99a1
    provide the complete decoder and the decoder back-end.  The JB2 scheme is
Packit df99a1
    optimized for images containing a large number of self-similar small
Packit df99a1
    components such as characters.  Typical text images can be compressed into
Packit df99a1
    files 3 to 5 times smaller than with G4/MMR and 2 to 4 times smaller than
Packit df99a1
    with JBIG1.
Packit df99a1
Packit df99a1
    {\bf JB2 and JBIG2} --- JB2 has strong similarities with the forthcoming
Packit df99a1
    JBIG2 standard developed by the "ISO/IEC JTC1 SC29 Working Group 1" which
Packit df99a1
    is responsible for both the JPEG and JBIG standards.  This is hardly
Packit df99a1
    surprising since JB2 was our own proposal for the JBIG2 standard
Packit df99a1
    and remained the only proposal for years.  The full JBIG2 standard however
Packit df99a1
    is significantly more complex and slighlty less efficient than JB2 because
Packit df99a1
    it addresses a broader range of applications.  Full JBIG2 compliance may
Packit df99a1
    be implemented in the future.
Packit df99a1
Packit df99a1
    {\bf JB2 Images} --- Class \Ref{JB2Image} is the central data structure
Packit df99a1
    implemented here.  A #JB2Image# is composed of an array of shapes
Packit df99a1
    and an array of blits.  Each shape contains a small bitmap representing an
Packit df99a1
    elementary blob of ink, such as a character or a segment of line art.
Packit df99a1
    Each blit instructs the decoder to render a particular shape at a
Packit df99a1
    specified position in the image.  Some compression is already achieved
Packit df99a1
    because several blits can refer to the same shape.  A shape can also
Packit df99a1
    contain a pointer to a parent shape.  Additional compression is achieved
Packit df99a1
    when both shapes are similar because each shape is encoded using the
Packit df99a1
    parent shape as a model.  A #"O"# shape for instance could be a parent for
Packit df99a1
    both a #"C"# shape and a #"Q"# shape.
Packit df99a1
Packit df99a1
    {\bf JB2 Dictionary} --- Class \Ref{JB2Dict} is a peculiar kind of
Packit df99a1
    JB2Image which only contains an array of shapes.  These shapes can be
Packit df99a1
    referenced from another JB2Dict/JB2Image.  This is arranged by setting the
Packit df99a1
    ``inherited dictionary'' of a JB2Dict/JB2Image using function
Packit df99a1
    \Ref{JB2Dict::set_inherited_dict}. Several JB2Images can use shapes from a
Packit df99a1
    same JB2Dict encoded separately.  This is how several pages of a same
Packit df99a1
    document can share information.
Packit df99a1
    
Packit df99a1
    {\bf Decoding JB2 data} --- The first step for decoding JB2 data consists of 
Packit df99a1
    creating an empty #JB2Image# object.  Function \Ref{JB2Image::decode} then
Packit df99a1
    reads the data and populates the #JB2Image# with the shapes and the blits.
Packit df99a1
    Function \Ref{JB2Image::get_bitmap} finally produces an anti-aliased image.
Packit df99a1
Packit df99a1
    {\bf Encoding JB2 data} --- The first step for decoding JB2 data also
Packit df99a1
    consists of creating an empty #JB2Image# object.  You must then use
Packit df99a1
    functions \Ref{JB2Image::add_shape} and \Ref{JB2Image::add_blit} to
Packit df99a1
    populate the #JB2Image# object.  Function \Ref{JB2Image::encode} finally
Packit df99a1
    produces the JB2 data.  Function #encode# sequentially encodes the blits
Packit df99a1
    and the necessary shapes.  The compression ratio depends on several
Packit df99a1
    factors:
Packit df99a1
    \begin{itemize}
Packit df99a1
    \item Blits should reuse shapes as often as possible.
Packit df99a1
    \item Blits should be sorted in reading order because this facilitates
Packit df99a1
          the prediction of the blit coordinates.
Packit df99a1
    \item Shapes should be sorted according to the order of first appearance
Packit df99a1
          in the sequence of blits because this facilitates the prediction of the
Packit df99a1
          shape indices.
Packit df99a1
    \item Shapes should be compared to all previous shapes in the shape array.
Packit df99a1
          The shape parent pointer should be set to a suitable parent shape if
Packit df99a1
          such a parent shape exists.  The parent shape should have almost the
Packit df99a1
          same size and the same pixels.
Packit df99a1
    \end{itemize}
Packit df99a1
    All this is quite easy to achieve in the case of an electronically
Packit df99a1
    produced document such as a DVI file or a PS file: we know what the
Packit df99a1
    characters are and where they are located.  If you only have a scanned
Packit df99a1
    image however you must first locate the characters (connected component
Packit df99a1
    analysis) and cut the remaining pieces of ink into smaller blobs.
Packit df99a1
    Ordering the blits and matching the shapes is then an essentially
Packit df99a1
    heuristic process.  Although the quality of the heuristics substantially
Packit df99a1
    effects the file size, misordering blits or mismatching shapes never
Packit df99a1
    effects the quality of the image.  The last refinement consists in
Packit df99a1
    smoothing the shapes in order to reduce the noise and maximize the
Packit df99a1
    similarities between shapes.
Packit df99a1
    
Packit df99a1
    {\bf JB2 extensions} --- Two extensions of the JB2
Packit df99a1
    encoding format have been introduced with DjVu files version 21. The first
Packit df99a1
    extension addresses the shared shape dictionaries. The second extension
Packit df99a1
    bounds the number of probability contexts used for coding numbers.
Packit df99a1
    Both extensions maintain backward compatibility with JB2 as 
Packit df99a1
    described in the ICFDD proposal. A more complete discussion
Packit df99a1
    can be found in section \Ref{JB2 extensions for version 21.}.
Packit df99a1
Packit df99a1
    {\bf References} 
Packit df99a1
    \begin{itemize}
Packit df99a1
    \item Paul G. Howard : {\em Text image compression using soft 
Packit df99a1
          pattern matching}, Computer Journal, volume 40:2/3, 1997.
Packit df99a1
    \item JBIG1 : \URL{http://www.jpeg.org/public/jbighomepage.htm}.
Packit df99a1
    \item JBIG2 draft : \URL{http://www.jpeg.org/public/jbigpt2.htm}.
Packit df99a1
    \item ICFDD Draft Proposed American National Standard, 1999-08-26.
Packit df99a1
    \end{itemize}
Packit df99a1
Packit df99a1
    @memo
Packit df99a1
    Coding bilevel images with JB2.
Packit df99a1
    @author
Packit df99a1
    Paul Howard <pgh@research.att.com> -- JB2 design\\
Packit df99a1
    L\'eon Bottou <leonb@research.att.com> -- this implementation 
Packit df99a1
Packit df99a1
// From: Leon Bottou, 1/31/2002
Packit df99a1
// Lizardtech has split the corresponding cpp file into a decoder and an encoder.
Packit df99a1
// Only superficial changes.  The meat is mine.
Packit df99a1
Packit df99a1
*/
Packit df99a1
//@{
Packit df99a1
Packit df99a1
Packit df99a1
#include "GString.h"
Packit df99a1
#include "ZPCodec.h"
Packit df99a1
Packit df99a1
Packit df99a1
#ifdef HAVE_NAMESPACES
Packit df99a1
namespace DJVU {
Packit df99a1
# ifdef NOT_DEFINED // Just to fool emacs c++ mode
Packit df99a1
}
Packit df99a1
#endif
Packit df99a1
#endif
Packit df99a1
Packit df99a1
class JB2Dict;
Packit df99a1
class JB2Image;
Packit df99a1
class GRect;
Packit df99a1
class GBitmap;
Packit df99a1
class ByteStream;
Packit df99a1
Packit df99a1
/** Blit data structure.  A #JB2Image# contains an array of #JB2Blit# data
Packit df99a1
    structures.  Each array entry instructs the decoder to render a particular
Packit df99a1
    shape at a particular location.  Members #left# and #bottom# specify the
Packit df99a1
    coordinates of the bottom left corner of the shape bitmap.  All
Packit df99a1
    coordinates are relative to the bottom left corner of the image.  Member
Packit df99a1
    #shapeno# is the subscript of the shape to be rendered.  */
Packit df99a1
Packit df99a1
class DJVUAPI JB2Blit {
Packit df99a1
public:
Packit df99a1
  /** Horizontal coordinate of the blit. */
Packit df99a1
  unsigned short left;
Packit df99a1
  /** Vertical coordinate of the blit. */
Packit df99a1
  unsigned short bottom;
Packit df99a1
  /** Index of the shape to blit. */
Packit df99a1
  unsigned int shapeno;
Packit df99a1
};
Packit df99a1
Packit df99a1
Packit df99a1
/** Shape data structure.  A #JB2Image# contains an array of #JB2Shape# data
Packit df99a1
    structures.  Each array entry represents an elementary blob of ink such as
Packit df99a1
    a character or a segment of line art.  Member #bits# points to a bilevel
Packit df99a1
    image representing the shape pixels.  Member #parent# is the subscript of
Packit df99a1
    the parent shape.  */
Packit df99a1
Packit df99a1
class DJVUAPI JB2Shape
Packit df99a1
{ 
Packit df99a1
public: 
Packit df99a1
  /** Subscript of the parent shape.  The parent shape must always be located
Packit df99a1
      before the current shape in the shape array.  A negative value indicates
Packit df99a1
      that this shape has no parent.  Any negative values smaller than #-1#
Packit df99a1
      further indicates that this shape does not look like a character.  This
Packit df99a1
      is used to enable a few internal optimizations.  This information is
Packit df99a1
      saved into the JB2 file, but the actual value of the #parent# variable
Packit df99a1
      is not. */
Packit df99a1
  int parent; 
Packit df99a1
  /** Bilevel image of the shape pixels.  This must be a pointer to a bilevel
Packit df99a1
      #GBitmap# image.  This pointer can also be null. The encoder will just
Packit df99a1
      silently discard all blits referring to a shape containing a null
Packit df99a1
      bitmap. */
Packit df99a1
  GP<GBitmap> bits;
Packit df99a1
  /** Private user data. This long word is provided as a convenience for users
Packit df99a1
      of the JB2Image data structures.  Neither the rendering functions nor
Packit df99a1
      the coding functions ever access this value. */
Packit df99a1
  long userdata;
Packit df99a1
};
Packit df99a1
Packit df99a1
Packit df99a1
Packit df99a1
/** JB2 Dictionary callback.
Packit df99a1
    The decoding function call this callback function when they discover that
Packit df99a1
    the current JB2Image or JB2Dict needs a pre-existing shape dictionary. 
Packit df99a1
    The callback function must return a pointer to the dictionary or NULL
Packit df99a1
    if none is found. */
Packit df99a1
Packit df99a1
typedef GP<JB2Dict> JB2DecoderCallback ( void* );
Packit df99a1
Packit df99a1
Packit df99a1
/** Dictionary of JB2 shapes. */
Packit df99a1
Packit df99a1
class DJVUAPI JB2Dict : public GPEnabled
Packit df99a1
{
Packit df99a1
protected:
Packit df99a1
  JB2Dict(void);
Packit df99a1
public:
Packit df99a1
  class JB2Codec;
Packit df99a1
Packit df99a1
  // CONSTRUCTION
Packit df99a1
  /** Default creator.  Constructs an empty #JB2Dict# object.  You can then
Packit df99a1
      call the decoding function #decode#.  You can also manually set the
Packit df99a1
      image size using #add_shape#. */
Packit df99a1
  static GP<JB2Dict> create(void);
Packit df99a1
Packit df99a1
  // INITIALIZATION
Packit df99a1
  /** Resets the #JB2Image# object.  This function reinitializes both the shape
Packit df99a1
     and the blit arrays.  All allocated memory is freed. */
Packit df99a1
  void init(void);
Packit df99a1
Packit df99a1
  // INHERITED
Packit df99a1
  /** Returns the inherited dictionary. */
Packit df99a1
  GP<JB2Dict> get_inherited_dict(void) const;
Packit df99a1
  /** Returns the number of inherited shapes. */
Packit df99a1
  int get_inherited_shape_count(void) const;
Packit df99a1
  /** Sets the inherited dictionary. */
Packit df99a1
  void set_inherited_dict(const GP<JB2Dict> &dict);
Packit df99a1
Packit df99a1
  // ACCESSING THE SHAPE LIBRARY
Packit df99a1
  /** Returns the total number of shapes.
Packit df99a1
      Shape indices range from #0# to #get_shape_count()-1#. */
Packit df99a1
  int get_shape_count(void) const;
Packit df99a1
  /** Returns a pointer to shape #shapeno#.
Packit df99a1
      The returned pointer directly points into the shape array.
Packit df99a1
      This pointer can be used for reading or writing the shape data. */
Packit df99a1
  JB2Shape &get_shape(const int shapeno);
Packit df99a1
  /** Returns a constant pointer to shape #shapeno#.
Packit df99a1
      The returned pointer directly points into the shape array.
Packit df99a1
      This pointer can only be used for reading the shape data. */
Packit df99a1
  const JB2Shape &get_shape(const int shapeno) const;
Packit df99a1
  /** Appends a shape to the shape array.  This function appends a copy of
Packit df99a1
      shape #shape# to the shape array and returns the subscript of the new
Packit df99a1
      shape.  The subscript of the parent shape #shape.parent# must 
Packit df99a1
      actually designate an already existing shape. */
Packit df99a1
  int  add_shape(const JB2Shape &shape);
Packit df99a1
Packit df99a1
  // MEMORY OPTIMIZATION
Packit df99a1
  /** Compresses all shape bitmaps.  This function reduces the memory required
Packit df99a1
      by the #JB2Image# by calling \Ref{GBitmap::compress} on all shapes
Packit df99a1
      bitmaps.  This function is best called after decoding a #JB2Image#,
Packit df99a1
      because function \Ref{get_bitmap} can directly use the compressed
Packit df99a1
      bitmaps.  */
Packit df99a1
  void compress(void);
Packit df99a1
  /** Returns the total memory used by the JB2Image.
Packit df99a1
      The returned value is expressed in bytes. */
Packit df99a1
  unsigned int get_memory_usage(void) const;
Packit df99a1
Packit df99a1
  // CODING
Packit df99a1
  /** Encodes the JB2Dict into ByteStream #bs#.  
Packit df99a1
      This function generates the JB2 data stream without any header.   */
Packit df99a1
  void encode(const GP<ByteStream> &gbs) const;
Packit df99a1
  /** Decodes JB2 data from ByteStream #bs#. This function decodes the image
Packit df99a1
      size and populates the shape and blit arrays.  The callback function
Packit df99a1
      #cb# is called when the decoder determines that the ByteStream data
Packit df99a1
      requires a shape dictionary which has not been set with
Packit df99a1
      \Ref{JB2Dict::set_inherited_dict}. The callback receives argument #arg#
Packit df99a1
      and must return a suitable dictionary which will be installed as the
Packit df99a1
      inherited dictionary.  The callback should return null if no such
Packit df99a1
      dictionary is found. */
Packit df99a1
  void decode(const GP<ByteStream> &gbs, JB2DecoderCallback *cb=0, void *arg=0);
Packit df99a1
Packit df99a1
  
Packit df99a1
public:
Packit df99a1
  /** Comment string coded by JB2 file. */
Packit df99a1
  GUTF8String comment;
Packit df99a1
Packit df99a1
Packit df99a1
private:
Packit df99a1
  friend class JB2Codec;
Packit df99a1
  int inherited_shapes;
Packit df99a1
  GP<JB2Dict> inherited_dict;
Packit df99a1
  GArray<JB2Shape> shapes;
Packit df99a1
Packit df99a1
  struct LibRect {
Packit df99a1
    int top,left,right,bottom;
Packit df99a1
    void compute_bounding_box(const GBitmap &cbm);
Packit df99a1
  };
Packit df99a1
  GTArray<LibRect> boxes;
Packit df99a1
  void get_bounding_box(int shapeno, LibRect &dest);
Packit df99a1
};
Packit df99a1
Packit df99a1
/** Main JB2 data structure.  Each #JB2Image# consists of an array of shapes
Packit df99a1
    and an array of blits.  These arrays can be populated by hand using
Packit df99a1
    functions \Ref{add_shape} and \Ref{add_blit}, or by decoding JB2 data
Packit df99a1
    using function \Ref{decode}.  You can then use function \Ref{get_bitmap}
Packit df99a1
    to render anti-aliased images, or use function \Ref{encode} to generate
Packit df99a1
    JB2 data. */
Packit df99a1
Packit df99a1
class DJVUAPI JB2Image : public JB2Dict
Packit df99a1
{
Packit df99a1
protected:
Packit df99a1
  JB2Image(void);
Packit df99a1
public:
Packit df99a1
Packit df99a1
  /** Creates an empty #JB2Image# object.  You can then
Packit df99a1
      call the decoding function #decode#.  You can also manually set the
Packit df99a1
      image size using #set_dimension# and populate the shape and blit arrays
Packit df99a1
      using #add_shape# and #add_blit#. */
Packit df99a1
  static GP<JB2Image> create(void) { return new JB2Image(); }
Packit df99a1
Packit df99a1
  // INITIALIZATION
Packit df99a1
  /** Resets the #JB2Image# object.  This function reinitializes both the shape
Packit df99a1
     and the blit arrays.  All allocated memory is freed. */
Packit df99a1
  void init(void);
Packit df99a1
Packit df99a1
  // DIMENSION
Packit df99a1
  /** Returns the width of the image.  
Packit df99a1
      This is the width value previously set with #set_dimension#. */
Packit df99a1
  int get_width(void) const;
Packit df99a1
  /** Returns the height of the image.  
Packit df99a1
      This is the height value previously set with #set_dimension#. */
Packit df99a1
  int get_height(void) const;
Packit df99a1
  /** Sets the size of the JB2Image.
Packit df99a1
      This function can be called at any time. 
Packit df99a1
      The corresponding #width# and the #height# are stored
Packit df99a1
      in the JB2 file. */
Packit df99a1
  void set_dimension(int width, int height);
Packit df99a1
Packit df99a1
  // RENDERING
Packit df99a1
  /** Renders an anti-aliased gray level image.  This function renders the
Packit df99a1
      JB2Image as a bilevel or gray level image.  Argument #subsample#
Packit df99a1
      specifies the desired subsampling ratio in range #1# to #15#.  The
Packit df99a1
      returned image uses #1+subsample^2# gray levels for representing
Packit df99a1
      anti-aliased edges.  Argument #align# specified the alignment of the
Packit df99a1
      rows of the returned images.  Setting #align# to #4#, for instance, will
Packit df99a1
      adjust the bitmap border in order to make sure that each row of the
Packit df99a1
      returned image starts on a word (four byte) boundary. */
Packit df99a1
  GP<GBitmap> get_bitmap(int subsample = 1, int align = 1) const;
Packit df99a1
  /** Renders an anti-aliased gray level sub-image.  This function renders a
Packit df99a1
      segment of the JB2Image as a bilevel or gray level image.  Conceptually,
Packit df99a1
      this function first renders the full JB2Image with subsampling ratio
Packit df99a1
      #subsample# and then extracts rectangle #rect# in the subsampled image.
Packit df99a1
      Both operations of course are efficiently performed simultaneously.
Packit df99a1
      Argument #align# specified the alignment of the rows of the returned
Packit df99a1
      images, as explained above.  Argument #dispy# should remain null. */
Packit df99a1
  GP<GBitmap> get_bitmap(const GRect &rect, int subsample=1, int align=1, int dispy=0) const;
Packit df99a1
Packit df99a1
  // ACCESSING THE BLIT LIBRARY
Packit df99a1
  /** Returns the total number of blits.
Packit df99a1
      Blit indices range from #0# to #get_blit_count(void)-1#. */
Packit df99a1
  int get_blit_count(void) const;
Packit df99a1
  /** Returns a pointer to blit #blitno#.
Packit df99a1
      The returned pointer directly points into the blit array.
Packit df99a1
      This pointer can be used for reading or writing the blit data. */
Packit df99a1
  JB2Blit *get_blit(int blitno);
Packit df99a1
  /** Returns a constant pointer to blit #blitno#.
Packit df99a1
      The returned pointer directly points into the shape array.
Packit df99a1
      This pointer can only be used for reading the shape data. */
Packit df99a1
  const JB2Blit *get_blit(int blitno) const;
Packit df99a1
  /** Appends a blit to the blit array.  This function appends a copy of blit
Packit df99a1
      #blit# to the blit array and returns the subscript of the new blit.  The
Packit df99a1
      shape subscript #blit.shapeno# must actually designate an already
Packit df99a1
      existing shape. */
Packit df99a1
  int  add_blit(const JB2Blit &blit);
Packit df99a1
Packit df99a1
  // MEMORY OPTIMIZATION
Packit df99a1
  /** Returns the total memory used by the JB2Image.
Packit df99a1
      The returned value is expressed in bytes. */
Packit df99a1
  unsigned int get_memory_usage(void) const;
Packit df99a1
Packit df99a1
  // CODING
Packit df99a1
  /** Encodes the JB2Image into ByteStream #bs#.  
Packit df99a1
      This function generates the JB2 data stream without any header. */
Packit df99a1
  void encode(const GP<ByteStream> &gbs) const;
Packit df99a1
  /** Decodes JB2 data from ByteStream #bs#. This function decodes the image
Packit df99a1
      size and populates the shape and blit arrays.  The callback function
Packit df99a1
      #cb# is called when the decoder determines that the ByteStream data
Packit df99a1
      requires a shape dictionary which has not been set with
Packit df99a1
      \Ref{JB2Dict::set_inherited_dict}. The callback receives argument #arg#
Packit df99a1
      and must return a suitable dictionary which will be installed as the
Packit df99a1
      inherited dictionary.  The callback should return null if no such
Packit df99a1
      dictionary is found. */
Packit df99a1
  void decode(const GP<ByteStream> &gbs, JB2DecoderCallback *cb=0, void *arg=0);
Packit df99a1
  
Packit df99a1
private:
Packit df99a1
  // Implementation
Packit df99a1
  int width;
Packit df99a1
  int height;
Packit df99a1
  GTArray<JB2Blit> blits;
Packit df99a1
public:
Packit df99a1
  /** Reproduces a old bug.  Setting this flag may be necessary for accurately
Packit df99a1
      decoding DjVu files with version smaller than #18#.  The default value
Packit df99a1
      is of couse #false#. */
Packit df99a1
  bool reproduce_old_bug;
Packit df99a1
};
Packit df99a1
Packit df99a1
Packit df99a1
Packit df99a1
// JB2DICT INLINE FUNCTIONS
Packit df99a1
Packit df99a1
inline int
Packit df99a1
JB2Dict::get_shape_count(void) const
Packit df99a1
{
Packit df99a1
  return inherited_shapes + shapes.size();
Packit df99a1
}
Packit df99a1
Packit df99a1
inline int
Packit df99a1
JB2Dict::get_inherited_shape_count(void) const
Packit df99a1
{
Packit df99a1
  return inherited_shapes;
Packit df99a1
}
Packit df99a1
Packit df99a1
inline GP<JB2Dict>
Packit df99a1
JB2Dict::get_inherited_dict(void) const
Packit df99a1
{
Packit df99a1
  return inherited_dict;
Packit df99a1
}
Packit df99a1
Packit df99a1
// JB2IMAGE INLINE FUNCTIONS
Packit df99a1
Packit df99a1
inline int
Packit df99a1
JB2Image::get_width(void) const
Packit df99a1
{
Packit df99a1
  return width;
Packit df99a1
}
Packit df99a1
Packit df99a1
inline int
Packit df99a1
JB2Image::get_height(void) const
Packit df99a1
{
Packit df99a1
  return height;
Packit df99a1
}
Packit df99a1
Packit df99a1
Packit df99a1
inline int
Packit df99a1
JB2Image::get_blit_count(void) const
Packit df99a1
{
Packit df99a1
  return blits.size();
Packit df99a1
}
Packit df99a1
Packit df99a1
Packit df99a1
inline JB2Blit *
Packit df99a1
JB2Image::get_blit(int blitno)
Packit df99a1
{
Packit df99a1
  return & blits[blitno];
Packit df99a1
}
Packit df99a1
Packit df99a1
inline const JB2Blit *
Packit df99a1
JB2Image::get_blit(int blitno) const
Packit df99a1
{
Packit df99a1
  return & blits[blitno];
Packit df99a1
}
Packit df99a1
Packit df99a1
Packit df99a1
Packit df99a1
Packit df99a1
Packit df99a1
/** @name JB2 extensions for version 21.
Packit df99a1
Packit df99a1
    Two extensions of the JB2 encoding format have been introduced
Packit df99a1
    with DjVu files version 21.  Both extensions maintain significant
Packit df99a1
    backward compatibility with previous version of the JB2 format.
Packit df99a1
    These extensions are described below by reference to the ICFDD
Packit df99a1
    proposal dated August 1999.  Both extension make use of the unused
Packit df99a1
    record type value #9# (cf. ICFDD page 24) which has been renamed
Packit df99a1
    #REQUIRED_DICT_OR_RESET#.
Packit df99a1
Packit df99a1
    {\bf Shared Shape Dictionaries} --- This extension provides
Packit df99a1
    support for sharing symbol definitions between the pages of a
Packit df99a1
    document.  To achieve this objective, the JB2 image data chunk
Packit df99a1
    must be able to address symbols defined elsewhere by a JB2
Packit df99a1
    dictionary data chunk shared by all the pages of a document.
Packit df99a1
Packit df99a1
    The arithmetically encoded JB2 image data logically consist of a
Packit df99a1
    sequence of records. The decoder processes these records in
Packit df99a1
    sequence and maintains a library of symbols which can be addressed
Packit df99a1
    by the following records.  The first record usually is a ``Start
Packit df99a1
    Of Image'' record describing the size of the image.
Packit df99a1
Packit df99a1
    Starting with version 21, a #REQUIRED_DICT_OR_RESET# (9) record
Packit df99a1
    type can appear {\em before} the #START_OF_DATA# (0) record.  The
Packit df99a1
    record type field is followed by a single number arithmetically
Packit df99a1
    encoded (cf. ICFDD page 26) using a sixteenth context (cf. ICFDD
Packit df99a1
    page 25).  This record appears when the JB2 data chunk requires
Packit df99a1
    symbols encoded in a separate JB2 dictionary data chunk.  The
Packit df99a1
    number (the {\bf dictionary size}) indicates how many symbols
Packit df99a1
    should have been defined by the JB2 dictionary data chunk.  The
Packit df99a1
    decoder should simply load these symbols in the symbol library and
Packit df99a1
    proceed as usual.  New symbols potentially defined by the
Packit df99a1
    subsequent JB2 image data records will therefore be numbered with
Packit df99a1
    integers greater or equal than the dictionary size.
Packit df99a1
Packit df99a1
    The JB2 dictionary data format is a pure subset of the JB2 image
Packit df99a1
    data format.  The #START_OF_DATA# (0) record always specifies an
Packit df99a1
    image width of zero and an image height of zero.  The only allowed
Packit df99a1
    record types are those defining library symbols only
Packit df99a1
    (#NEW_SYMBOL_LIBRARY_ONLY# (2) and #MATCHED_REFINE_LIBRARY_ONLY#
Packit df99a1
    (5) cf. ICFDD page 24) followed by a final #END_OF_DATA# (11)
Packit df99a1
    record.
Packit df99a1
Packit df99a1
    The JB2 dictionary data is usually located in an {\bf Djbz} chunk.
Packit df99a1
    Each page {\bf FORM:DJVU} may directly contain a {\bf Djbz} chunk,
Packit df99a1
    or may indirectly point to such a chunk using an {\bf INCL} chunk
Packit df99a1
    (cf. \Ref{Multipage DjVu documents.}).
Packit df99a1
    
Packit df99a1
Packit df99a1
    {\bf Numcoder Reset} --- This extension addresses a problem for
Packit df99a1
    hardware implementations.  The encoding of numbers (cf. ICFDD page
Packit df99a1
    26) potentially uses an unbounded number of binary coding
Packit df99a1
    contexts. These contexts are normally allocated when they are used
Packit df99a1
    for the first time (cf. ICFDD informative note, page 27).
Packit df99a1
Packit df99a1
    Starting with version 21, a #REQUIRED_DICT_OR_RESET# (9) record
Packit df99a1
    type can appear {\em after} the #START_OF_DATA# (0) record.  The
Packit df99a1
    decoder should proceed with the next record after {\em clearing
Packit df99a1
    all binary contexts used for coding numbers}.  This operation
Packit df99a1
    implies that all binary contexts previously allocated for coding
Packit df99a1
    numbers can be deallocated.
Packit df99a1
  
Packit df99a1
    Starting with version 21, the JB2 encoder should insert a
Packit df99a1
    #REQUIRED_DICT_OR_RESET# record type whenever the number of these
Packit df99a1
    allocated binary contexts exceeds #20000#.  Only very large
Packit df99a1
    documents ever reach such a large number of allocated binary
Packit df99a1
    contexts (e.g large maps).  Hardware implementation however can
Packit df99a1
    benefit greatly from a hard bound on the total number of binary
Packit df99a1
    coding contexts.  Old JB2 decoders will treat this record type as
Packit df99a1
    an #END_OF_DATA# record and cleanly stop decoding (cf. ICFDD page
Packit df99a1
    30, Image refinement data).
Packit df99a1
Packit df99a1
Packit df99a1
    {\bf References} ---
Packit df99a1
    \begin{itemize}
Packit df99a1
    \item ICFDD Draft Proposed American National Standard, 1999-08-26.
Packit df99a1
    \item DjVu Specification, \URL{http://www.lizardtech.com/djvu/sci/djvuspec}.
Packit df99a1
    \end{itemize}
Packit df99a1
Packit df99a1
    @memo Extensions to the JB2 format introduced in version 21.  */
Packit df99a1
Packit df99a1
//@}
Packit df99a1
Packit df99a1
////////////////////////////////////////
Packit df99a1
//// CLASS JB2CODEC:  DECLARATION
Packit df99a1
////////////////////////////////////////
Packit df99a1
Packit df99a1
// This class is accessed via the encode and decode
Packit df99a1
// functions of class JB2Image
Packit df99a1
Packit df99a1
Packit df99a1
//**** Class JB2Codec
Packit df99a1
// This class implements the base class for both the JB2 coder and decoder.
Packit df99a1
// The JB2Codec's Contains all contextual information for encoding/decoding
Packit df99a1
// a JB2Image.
Packit df99a1
Packit df99a1
class JB2Dict::JB2Codec
Packit df99a1
{
Packit df99a1
public:
Packit df99a1
  class Decode;
Packit df99a1
  class Encode;
Packit df99a1
  typedef unsigned int NumContext;
Packit df99a1
  virtual ~JB2Codec();
Packit df99a1
protected:
Packit df99a1
  // Constructors
Packit df99a1
  JB2Codec(const bool xencoding=false);
Packit df99a1
  // Forbidden assignment
Packit df99a1
  JB2Codec(const JB2Codec &ref;;
Packit df99a1
  JB2Codec& operator=(const JB2Codec &ref;;
Packit df99a1
Packit df99a1
  int CodeNum(int lo, int hi, NumContext *pctx,int v);
Packit df99a1
  void reset_numcoder(void);
Packit df99a1
  inline void code_eventual_lossless_refinement(void);
Packit df99a1
  void init_library(JB2Dict &jim);
Packit df99a1
  int add_library(const int shapeno, JB2Shape &jshp);
Packit df99a1
  void code_relative_location(JB2Blit *jblt, int rows, int columns);
Packit df99a1
  void code_bitmap_directly (GBitmap &bm;;
Packit df99a1
  void code_bitmap_by_cross_coding (GBitmap &bm, GP<GBitmap> &cbm, const int libno);
Packit df99a1
  void code_record(int &rectype, const GP<JB2Dict> &jim, JB2Shape *jshp);
Packit df99a1
  void code_record(int &rectype, const GP<JB2Image> &jim, JB2Shape *jshp, JB2Blit *jblt);
Packit df99a1
  static void compute_bounding_box(GBitmap &cbm, LibRect &lrect);
Packit df99a1
  static int get_direct_context( unsigned char const * const up2,
Packit df99a1
    unsigned char const * const up1, unsigned char const * const up0,
Packit df99a1
    const int column);
Packit df99a1
  static int shift_direct_context ( const int context,
Packit df99a1
    const int next, unsigned char const * const up2,
Packit df99a1
    unsigned char const * const up1, unsigned char const * const up0,
Packit df99a1
    const int column);
Packit df99a1
  static int get_cross_context( unsigned char const * const up1,
Packit df99a1
    unsigned char const * const up0, unsigned char const * const xup1,
Packit df99a1
    unsigned char const * const xup0, unsigned char const * const xdn1,
Packit df99a1
    const int column );
Packit df99a1
  static int shift_cross_context( const int context,
Packit df99a1
    const int n, unsigned char const * const up1,
Packit df99a1
    unsigned char const * const up0, unsigned char const * const xup1,
Packit df99a1
    unsigned char const * const xup0, unsigned char const * const xdn1,
Packit df99a1
    const int column );
Packit df99a1
Packit df99a1
  virtual bool CodeBit(const bool bit, BitContext &ctx) = 0;
Packit df99a1
  virtual void code_comment(GUTF8String &comment) = 0;
Packit df99a1
  virtual void code_record_type(int &rectype) = 0;
Packit df99a1
  virtual int code_match_index(int &index, JB2Dict &jim)=0;
Packit df99a1
  virtual void code_inherited_shape_count(JB2Dict &jim)=0;
Packit df99a1
  virtual void code_image_size(JB2Dict &jim);
Packit df99a1
  virtual void code_image_size(JB2Image &jim);
Packit df99a1
  virtual void code_absolute_location(JB2Blit *jblt,  int rows, int columns)=0;
Packit df99a1
  virtual void code_absolute_mark_size(GBitmap &bm, int border=0) = 0;
Packit df99a1
  virtual void code_relative_mark_size(GBitmap &bm, int cw, int ch, int border=0) = 0;
Packit df99a1
  virtual void code_bitmap_directly(GBitmap &bm,const int dw, int dy,
Packit df99a1
    unsigned char *up2, unsigned char *up1, unsigned char *up0 )=0;
Packit df99a1
  virtual void code_bitmap_by_cross_coding (GBitmap &bm, GBitmap &cbm,
Packit df99a1
    const int xd2c, const int dw, int dy, int cy,
Packit df99a1
    unsigned char *up1, unsigned char *up0, unsigned char *xup1, 
Packit df99a1
    unsigned char *xup0, unsigned char *xdn1 )=0;
Packit df99a1
  // Code records
Packit df99a1
  virtual int get_diff(const int x_diff,NumContext &rel_loc) = 0;
Packit df99a1
Packit df99a1
private:
Packit df99a1
  bool encoding;
Packit df99a1
Packit df99a1
protected:
Packit df99a1
  // NumCoder
Packit df99a1
  int cur_ncell;
Packit df99a1
  BitContext *bitcells;
Packit df99a1
  GPBuffer<BitContext> gbitcells;
Packit df99a1
  NumContext *leftcell;
Packit df99a1
  GPBuffer<NumContext> gleftcell;
Packit df99a1
  NumContext *rightcell;
Packit df99a1
  GPBuffer<NumContext> grightcell;
Packit df99a1
  // Info
Packit df99a1
  bool refinementp;
Packit df99a1
  char gotstartrecordp;
Packit df99a1
  // Code comment
Packit df99a1
  NumContext dist_comment_byte;
Packit df99a1
  NumContext dist_comment_length;
Packit df99a1
  // Code values
Packit df99a1
  NumContext dist_record_type;
Packit df99a1
  NumContext dist_match_index;
Packit df99a1
  BitContext dist_refinement_flag;
Packit df99a1
  // Library
Packit df99a1
  GTArray<int> shape2lib;
Packit df99a1
  GTArray<int> lib2shape;
Packit df99a1
  GTArray<LibRect> libinfo;
Packit df99a1
  // Code pairs
Packit df99a1
  NumContext abs_loc_x;
Packit df99a1
  NumContext abs_loc_y;
Packit df99a1
  NumContext abs_size_x;
Packit df99a1
  NumContext abs_size_y;
Packit df99a1
  NumContext image_size_dist;
Packit df99a1
  NumContext inherited_shape_count_dist;
Packit df99a1
  BitContext offset_type_dist;
Packit df99a1
  NumContext rel_loc_x_current;
Packit df99a1
  NumContext rel_loc_x_last;
Packit df99a1
  NumContext rel_loc_y_current;
Packit df99a1
  NumContext rel_loc_y_last;
Packit df99a1
  NumContext rel_size_x;
Packit df99a1
  NumContext rel_size_y;
Packit df99a1
  int last_bottom;
Packit df99a1
  int last_left;
Packit df99a1
  int last_right;
Packit df99a1
  int last_row_bottom;
Packit df99a1
  int last_row_left;
Packit df99a1
  int image_columns;
Packit df99a1
  int image_rows;
Packit df99a1
  int short_list[3];
Packit df99a1
  int short_list_pos;
Packit df99a1
  inline void fill_short_list(const int v);
Packit df99a1
  int update_short_list(const int v);
Packit df99a1
  // Code bitmaps
Packit df99a1
  BitContext bitdist[1024];
Packit df99a1
  BitContext cbitdist[2048];
Packit df99a1
};
Packit df99a1
Packit df99a1
inline void
Packit df99a1
JB2Dict::JB2Codec::code_eventual_lossless_refinement(void)
Packit df99a1
{
Packit df99a1
  refinementp=CodeBit(refinementp, dist_refinement_flag);
Packit df99a1
}
Packit df99a1
Packit df99a1
inline void
Packit df99a1
JB2Dict::JB2Codec::fill_short_list(const int v)
Packit df99a1
{
Packit df99a1
  short_list[0] = short_list[1] = short_list[2] = v;
Packit df99a1
  short_list_pos = 0;
Packit df99a1
}
Packit df99a1
Packit df99a1
inline int
Packit df99a1
JB2Dict::JB2Codec::get_direct_context( unsigned char const * const up2,
Packit df99a1
                    unsigned char const * const up1,
Packit df99a1
                    unsigned char const * const up0,
Packit df99a1
                    const int column)
Packit df99a1
{
Packit df99a1
  return ( (up2[column - 1] << 9) |
Packit df99a1
              (up2[column    ] << 8) |
Packit df99a1
              (up2[column + 1] << 7) |
Packit df99a1
              (up1[column - 2] << 6) |
Packit df99a1
              (up1[column - 1] << 5) |
Packit df99a1
              (up1[column    ] << 4) |
Packit df99a1
              (up1[column + 1] << 3) |
Packit df99a1
              (up1[column + 2] << 2) |
Packit df99a1
              (up0[column - 2] << 1) |
Packit df99a1
              (up0[column - 1] << 0) );
Packit df99a1
}
Packit df99a1
Packit df99a1
inline int
Packit df99a1
JB2Dict::JB2Codec::shift_direct_context(const int context, const int next,
Packit df99a1
                     unsigned char const * const up2,
Packit df99a1
                     unsigned char const * const up1,
Packit df99a1
                     unsigned char const * const up0,
Packit df99a1
                     const int column)
Packit df99a1
{
Packit df99a1
  return ( ((context << 1) & 0x37a) |
Packit df99a1
              (up1[column + 2] << 2)   |
Packit df99a1
              (up2[column + 1] << 7)   |
Packit df99a1
              (next << 0)              );
Packit df99a1
}
Packit df99a1
Packit df99a1
inline int
Packit df99a1
JB2Dict::JB2Codec::get_cross_context( unsigned char const * const up1,
Packit df99a1
                   unsigned char const * const up0,
Packit df99a1
                   unsigned char const * const xup1,
Packit df99a1
                   unsigned char const * const xup0,
Packit df99a1
                   unsigned char const * const xdn1,
Packit df99a1
                   const int column )
Packit df99a1
{
Packit df99a1
  return ( ( up1[column - 1] << 10) |
Packit df99a1
              ( up1[column    ] <<  9) |
Packit df99a1
              ( up1[column + 1] <<  8) |
Packit df99a1
              ( up0[column - 1] <<  7) |
Packit df99a1
              (xup1[column    ] <<  6) |
Packit df99a1
              (xup0[column - 1] <<  5) |
Packit df99a1
              (xup0[column    ] <<  4) |
Packit df99a1
              (xup0[column + 1] <<  3) |
Packit df99a1
              (xdn1[column - 1] <<  2) |
Packit df99a1
              (xdn1[column    ] <<  1) |
Packit df99a1
              (xdn1[column + 1] <<  0) );
Packit df99a1
}
Packit df99a1
Packit df99a1
inline int
Packit df99a1
JB2Dict::JB2Codec::shift_cross_context( const int context, const int n,
Packit df99a1
                     unsigned char const * const up1,
Packit df99a1
                     unsigned char const * const up0,
Packit df99a1
                     unsigned char const * const xup1,
Packit df99a1
                     unsigned char const * const xup0,
Packit df99a1
                     unsigned char const * const xdn1,
Packit df99a1
                     const int column )
Packit df99a1
{
Packit df99a1
  return ( ((context<<1) & 0x636)  |
Packit df99a1
              ( up1[column + 1] << 8) |
Packit df99a1
              (xup1[column    ] << 6) |
Packit df99a1
              (xup0[column + 1] << 3) |
Packit df99a1
              (xdn1[column + 1] << 0) |
Packit df99a1
              (n << 7)             );
Packit df99a1
}
Packit df99a1
Packit df99a1
// ---------- THE END
Packit df99a1
Packit df99a1
#ifdef HAVE_NAMESPACES
Packit df99a1
}
Packit df99a1
# ifndef NOT_USING_DJVU_NAMESPACE
Packit df99a1
using namespace DJVU;
Packit df99a1
# endif
Packit df99a1
#endif
Packit df99a1
#endif
Packit df99a1