Viewing File: <root>/src/lib/util/chd.h

    1  /***************************************************************************
    2  
    3      chd.h
    4  
    5      MAME Compressed Hunks of Data file format
    6  
    7  ****************************************************************************
    8  
    9      Copyright Aaron Giles
   10      All rights reserved.
   11  
   12      Redistribution and use in source and binary forms, with or without
   13      modification, are permitted provided that the following conditions are
   14      met:
   15  
   16          * Redistributions of source code must retain the above copyright
   17            notice, this list of conditions and the following disclaimer.
   18          * Redistributions in binary form must reproduce the above copyright
   19            notice, this list of conditions and the following disclaimer in
   20            the documentation and/or other materials provided with the
   21            distribution.
   22          * Neither the name 'MAME' nor the names of its contributors may be
   23            used to endorse or promote products derived from this software
   24            without specific prior written permission.
   25  
   26      THIS SOFTWARE IS PROVIDED BY AARON GILES ''AS IS'' AND ANY EXPRESS OR
   27      IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
   28      WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
   29      DISCLAIMED. IN NO EVENT SHALL AARON GILES BE LIABLE FOR ANY DIRECT,
   30      INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
   31      (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
   32      SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
   33      HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
   34      STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
   35      IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
   36      POSSIBILITY OF SUCH DAMAGE.
   37  
   38  ***************************************************************************/
   39  
   40  #pragma once
   41  
   42  #ifndef __CHD_H__
   43  #define __CHD_H__
   44  
   45  #include "osdcore.h"
   46  #include "coretmpl.h"
   47  #include "astring.h"
   48  #include "bitmap.h"
   49  #include "corefile.h"
   50  #include "hashing.h"
   51  #include "chdcodec.h"
   52  
   53  
   54  /***************************************************************************
   55  
   56      Compressed Hunks of Data header format. All numbers are stored in
   57      Motorola (big-endian) byte ordering.
   58  
   59      =========================================================================
   60  
   61      V1 header:
   62  
   63      [  0] char   tag[8];        // 'MComprHD'
   64      [  8] UINT32 length;        // length of header (including tag and length fields)
   65      [ 12] UINT32 version;       // drive format version
   66      [ 16] UINT32 flags;         // flags (see below)
   67      [ 20] UINT32 compression;   // compression type
   68      [ 24] UINT32 hunksize;      // 512-byte sectors per hunk
   69      [ 28] UINT32 totalhunks;    // total # of hunks represented
   70      [ 32] UINT32 cylinders;     // number of cylinders on hard disk
   71      [ 36] UINT32 heads;         // number of heads on hard disk
   72      [ 40] UINT32 sectors;       // number of sectors on hard disk
   73      [ 44] UINT8  md5[16];       // MD5 checksum of raw data
   74      [ 60] UINT8  parentmd5[16]; // MD5 checksum of parent file
   75      [ 76] (V1 header length)
   76  
   77      Flags:
   78          0x00000001 - set if this drive has a parent
   79          0x00000002 - set if this drive allows writes
   80  
   81      Compression types:
   82          CHDCOMPRESSION_NONE = 0
   83          CHDCOMPRESSION_ZLIB = 1
   84  
   85      V1 map format:
   86  
   87      [  0] UINT64 offset : 44;   // starting offset within the file
   88      [  0] UINT64 length : 20;   // length of data; if == hunksize, data is uncompressed
   89  
   90      =========================================================================
   91  
   92      V2 header:
   93  
   94      [  0] char   tag[8];        // 'MComprHD'
   95      [  8] UINT32 length;        // length of header (including tag and length fields)
   96      [ 12] UINT32 version;       // drive format version
   97      [ 16] UINT32 flags;         // flags (see below)
   98      [ 20] UINT32 compression;   // compression type
   99      [ 24] UINT32 hunksize;      // seclen-byte sectors per hunk
  100      [ 28] UINT32 totalhunks;    // total # of hunks represented
  101      [ 32] UINT32 cylinders;     // number of cylinders on hard disk
  102      [ 36] UINT32 heads;         // number of heads on hard disk
  103      [ 40] UINT32 sectors;       // number of sectors on hard disk
  104      [ 44] UINT8  md5[16];       // MD5 checksum of raw data
  105      [ 60] UINT8  parentmd5[16]; // MD5 checksum of parent file
  106      [ 76] UINT32 seclen;        // number of bytes per sector
  107      [ 80] (V2 header length)
  108  
  109      Flags and map format are same as V1
  110  
  111      =========================================================================
  112  
  113      V3 header:
  114  
  115      [  0] char   tag[8];        // 'MComprHD'
  116      [  8] UINT32 length;        // length of header (including tag and length fields)
  117      [ 12] UINT32 version;       // drive format version
  118      [ 16] UINT32 flags;         // flags (see below)
  119      [ 20] UINT32 compression;   // compression type
  120      [ 24] UINT32 totalhunks;    // total # of hunks represented
  121      [ 28] UINT64 logicalbytes;  // logical size of the data (in bytes)
  122      [ 36] UINT64 metaoffset;    // offset to the first blob of metadata
  123      [ 44] UINT8  md5[16];       // MD5 checksum of raw data
  124      [ 60] UINT8  parentmd5[16]; // MD5 checksum of parent file
  125      [ 76] UINT32 hunkbytes;     // number of bytes per hunk
  126      [ 80] UINT8  sha1[20];      // SHA1 checksum of raw data
  127      [100] UINT8  parentsha1[20];// SHA1 checksum of parent file
  128      [120] (V3 header length)
  129  
  130      Flags are the same as V1
  131  
  132      Compression types:
  133          CHDCOMPRESSION_NONE = 0
  134          CHDCOMPRESSION_ZLIB = 1
  135          CHDCOMPRESSION_ZLIB_PLUS = 2
  136  
  137      V3 map format:
  138  
  139      [  0] UINT64 offset;        // starting offset within the file
  140      [  8] UINT32 crc32;         // 32-bit CRC of the uncompressed data
  141      [ 12] UINT16 length_lo;     // lower 16 bits of length
  142      [ 14] UINT8 length_hi;      // upper 8 bits of length
  143      [ 15] UINT8 flags;          // flags, indicating compression info
  144  
  145      =========================================================================
  146  
  147      V4 header:
  148  
  149      [  0] char   tag[8];        // 'MComprHD'
  150      [  8] UINT32 length;        // length of header (including tag and length fields)
  151      [ 12] UINT32 version;       // drive format version
  152      [ 16] UINT32 flags;         // flags (see below)
  153      [ 20] UINT32 compression;   // compression type
  154      [ 24] UINT32 totalhunks;    // total # of hunks represented
  155      [ 28] UINT64 logicalbytes;  // logical size of the data (in bytes)
  156      [ 36] UINT64 metaoffset;    // offset to the first blob of metadata
  157      [ 44] UINT32 hunkbytes;     // number of bytes per hunk
  158      [ 48] UINT8  sha1[20];      // combined raw+meta SHA1
  159      [ 68] UINT8  parentsha1[20];// combined raw+meta SHA1 of parent
  160      [ 88] UINT8  rawsha1[20];   // raw data SHA1
  161      [108] (V4 header length)
  162  
  163      Flags are the same as V1
  164  
  165      Compression types:
  166          CHDCOMPRESSION_NONE = 0
  167          CHDCOMPRESSION_ZLIB = 1
  168          CHDCOMPRESSION_ZLIB_PLUS = 2
  169          CHDCOMPRESSION_AV = 3
  170  
  171      Map format is the same as V3
  172  
  173      =========================================================================
  174  
  175      V5 header:
  176  
  177      [  0] char   tag[8];        // 'MComprHD'
  178      [  8] UINT32 length;        // length of header (including tag and length fields)
  179      [ 12] UINT32 version;       // drive format version
  180      [ 16] UINT32 compressors[4];// which custom compressors are used?
  181      [ 32] UINT64 logicalbytes;  // logical size of the data (in bytes)
  182      [ 40] UINT64 mapoffset;     // offset to the map
  183      [ 48] UINT64 metaoffset;    // offset to the first blob of metadata
  184      [ 56] UINT32 hunkbytes;     // number of bytes per hunk (512k maximum)
  185      [ 60] UINT32 unitbytes;     // number of bytes per unit within each hunk
  186      [ 64] UINT8  rawsha1[20];   // raw data SHA1
  187      [ 84] UINT8  sha1[20];      // combined raw+meta SHA1
  188      [104] UINT8  parentsha1[20];// combined raw+meta SHA1 of parent
  189      [124] (V5 header length)
  190  
  191      If parentsha1 != 0, we have a parent (no need for flags)
  192      If compressors[0] == 0, we are uncompressed (including maps)
  193  
  194      V5 uncompressed map format:
  195  
  196      [  0] UINT32 offset;        // starting offset / hunk size
  197  
  198      V5 compressed map format header:
  199  
  200      [  0] UINT32 length;        // length of compressed map
  201      [  4] UINT48 datastart;     // offset of first block
  202      [ 10] UINT16 crc;           // crc-16 of the map
  203      [ 12] UINT8 lengthbits;     // bits used to encode complength
  204      [ 13] UINT8 hunkbits;       // bits used to encode self-refs
  205      [ 14] UINT8 parentunitbits; // bits used to encode parent unit refs
  206      [ 15] UINT8 reserved;       // future use
  207      [ 16] (compressed header length)
  208  
  209      Each compressed map entry, once expanded, looks like:
  210  
  211      [  0] UINT8 compression;    // compression type
  212      [  1] UINT24 complength;    // compressed length
  213      [  4] UINT48 offset;        // offset
  214      [ 10] UINT16 crc;           // crc-16 of the data
  215  
  216  ***************************************************************************/
  217  
  218  
  219  //**************************************************************************
  220  //  CONSTANTS
  221  //**************************************************************************
  222  
  223  // pseudo-codecs returned by hunk_info
  224  const chd_codec_type CHD_CODEC_SELF         = 1;    // copy of another hunk
  225  const chd_codec_type CHD_CODEC_PARENT       = 2;    // copy of a parent's hunk
  226  const chd_codec_type CHD_CODEC_MINI         = 3;    // legacy "mini" 8-byte repeat
  227  
  228  // core types
  229  typedef UINT32 chd_metadata_tag;
  230  
  231  // metadata parameters
  232  const chd_metadata_tag CHDMETATAG_WILDCARD = 0;
  233  const UINT32 CHDMETAINDEX_APPEND = ~0;
  234  
  235  // metadata flags
  236  const UINT8 CHD_MDFLAGS_CHECKSUM = 0x01;        // indicates data is checksummed
  237  
  238  // standard hard disk metadata
  239  const chd_metadata_tag HARD_DISK_METADATA_TAG = CHD_MAKE_TAG('G','D','D','D');
  240  extern const char *HARD_DISK_METADATA_FORMAT;
  241  
  242  // hard disk identify information
  243  const chd_metadata_tag HARD_DISK_IDENT_METADATA_TAG = CHD_MAKE_TAG('I','D','N','T');
  244  
  245  // hard disk key information
  246  const chd_metadata_tag HARD_DISK_KEY_METADATA_TAG = CHD_MAKE_TAG('K','E','Y',' ');
  247  
  248  // pcmcia CIS information
  249  const chd_metadata_tag PCMCIA_CIS_METADATA_TAG = CHD_MAKE_TAG('C','I','S',' ');
  250  
  251  // standard CD-ROM metadata
  252  const chd_metadata_tag CDROM_OLD_METADATA_TAG = CHD_MAKE_TAG('C','H','C','D');
  253  const chd_metadata_tag CDROM_TRACK_METADATA_TAG = CHD_MAKE_TAG('C','H','T','R');
  254  extern const char *CDROM_TRACK_METADATA_FORMAT;
  255  const chd_metadata_tag CDROM_TRACK_METADATA2_TAG = CHD_MAKE_TAG('C','H','T','2');
  256  extern const char *CDROM_TRACK_METADATA2_FORMAT;
  257  const chd_metadata_tag GDROM_TRACK_METADATA_TAG = CHD_MAKE_TAG('C','H','G','T');
  258  extern const char *GDROM_TRACK_METADATA_FORMAT;
  259  
  260  // standard A/V metadata
  261  const chd_metadata_tag AV_METADATA_TAG = CHD_MAKE_TAG('A','V','A','V');
  262  extern const char *AV_METADATA_FORMAT;
  263  
  264  // A/V laserdisc frame metadata
  265  const chd_metadata_tag AV_LD_METADATA_TAG = CHD_MAKE_TAG('A','V','L','D');
  266  
  267  // error types
  268  enum chd_error
  269  {
  270      CHDERR_NONE,
  271      CHDERR_NO_INTERFACE,
  272      CHDERR_OUT_OF_MEMORY,
  273      CHDERR_NOT_OPEN,
  274      CHDERR_ALREADY_OPEN,
  275      CHDERR_INVALID_FILE,
  276      CHDERR_INVALID_PARAMETER,
  277      CHDERR_INVALID_DATA,
  278      CHDERR_FILE_NOT_FOUND,
  279      CHDERR_REQUIRES_PARENT,
  280      CHDERR_FILE_NOT_WRITEABLE,
  281      CHDERR_READ_ERROR,
  282      CHDERR_WRITE_ERROR,
  283      CHDERR_CODEC_ERROR,
  284      CHDERR_INVALID_PARENT,
  285      CHDERR_HUNK_OUT_OF_RANGE,
  286      CHDERR_DECOMPRESSION_ERROR,
  287      CHDERR_COMPRESSION_ERROR,
  288      CHDERR_CANT_CREATE_FILE,
  289      CHDERR_CANT_VERIFY,
  290      CHDERR_NOT_SUPPORTED,
  291      CHDERR_METADATA_NOT_FOUND,
  292      CHDERR_INVALID_METADATA_SIZE,
  293      CHDERR_UNSUPPORTED_VERSION,
  294      CHDERR_VERIFY_INCOMPLETE,
  295      CHDERR_INVALID_METADATA,
  296      CHDERR_INVALID_STATE,
  297      CHDERR_OPERATION_PENDING,
  298      CHDERR_UNSUPPORTED_FORMAT,
  299      CHDERR_UNKNOWN_COMPRESSION,
  300      CHDERR_WALKING_PARENT,
  301      CHDERR_COMPRESSING
  302  };
  303  
  304  
  305  
  306  //**************************************************************************
  307  //  TYPE DEFINITIONS
  308  //**************************************************************************
  309  
  310  class chd_codec;
  311  
  312  
  313  // ======================> chd_file
  314  
  315  // core file class
  316  class chd_file
  317  {
  318      friend class chd_file_compressor;
  319      friend class chd_verifier;
  320  
  321      // constants
  322      static const UINT32 HEADER_VERSION = 5;
  323      static const UINT32 V3_HEADER_SIZE = 120;
  324      static const UINT32 V4_HEADER_SIZE = 108;
  325      static const UINT32 V5_HEADER_SIZE = 124;
  326      static const UINT32 MAX_HEADER_SIZE = V5_HEADER_SIZE;
  327  
  328  public:
  329      // construction/destruction
  330      chd_file();
  331      virtual ~chd_file();
  332  
  333      // operators
  334      operator core_file *() { return m_file; }
  335  
  336      // getters
  337      bool opened() const { return (m_file != NULL); }
  338      UINT32 version() const { return m_version; }
  339      UINT64 logical_bytes() const { return m_logicalbytes; }
  340      UINT32 hunk_bytes() const { return m_hunkbytes; }
  341      UINT32 hunk_count() const { return m_hunkcount; }
  342      UINT32 unit_bytes() const { return m_unitbytes; }
  343      UINT64 unit_count() const { return m_unitcount; }
  344      bool compressed() const { return (m_compression[0] != CHD_CODEC_NONE); }
  345      chd_codec_type compression(int index) const { return m_compression[index]; }
  346      chd_file *parent() const { return m_parent; }
  347      sha1_t sha1();
  348      sha1_t raw_sha1();
  349      sha1_t parent_sha1();
  350      chd_error hunk_info(UINT32 hunknum, chd_codec_type &compressor, UINT32 &compbytes);
  351  
  352      // setters
  353      void set_raw_sha1(sha1_t rawdata);
  354      void set_parent_sha1(sha1_t parent);
  355  
  356      // file create
  357      chd_error create(const char *filename, UINT64 logicalbytes, UINT32 hunkbytes, UINT32 unitbytes, chd_codec_type compression[4]);
  358      chd_error create(core_file &file, UINT64 logicalbytes, UINT32 hunkbytes, UINT32 unitbytes, chd_codec_type compression[4]);
  359      chd_error create(const char *filename, UINT64 logicalbytes, UINT32 hunkbytes, chd_codec_type compression[4], chd_file &parent);
  360      chd_error create(core_file &file, UINT64 logicalbytes, UINT32 hunkbytes, chd_codec_type compression[4], chd_file &parent);
  361  
  362      // file open
  363      chd_error open(const char *filename, bool writeable = false, chd_file *parent = NULL);
  364      chd_error open(core_file &file, bool writeable = false, chd_file *parent = NULL);
  365  
  366      // file close
  367      void close();
  368  
  369      // read/write
  370      chd_error read_hunk(UINT32 hunknum, void *buffer);
  371      chd_error write_hunk(UINT32 hunknum, const void *buffer);
  372      chd_error read_units(UINT64 unitnum, void *buffer, UINT32 count = 1);
  373      chd_error write_units(UINT64 unitnum, const void *buffer, UINT32 count = 1);
  374      chd_error read_bytes(UINT64 offset, void *buffer, UINT32 bytes);
  375      chd_error write_bytes(UINT64 offset, const void *buffer, UINT32 bytes);
  376  
  377      // metadata management
  378      chd_error read_metadata(chd_metadata_tag searchtag, UINT32 searchindex, astring &output);
  379      chd_error read_metadata(chd_metadata_tag searchtag, UINT32 searchindex, dynamic_buffer &output);
  380      chd_error read_metadata(chd_metadata_tag searchtag, UINT32 searchindex, void *output, UINT32 outputlen, UINT32 &resultlen);
  381      chd_error read_metadata(chd_metadata_tag searchtag, UINT32 searchindex, dynamic_buffer &output, chd_metadata_tag &resulttag, UINT8 &resultflags);
  382      chd_error write_metadata(chd_metadata_tag metatag, UINT32 metaindex, const void *inputbuf, UINT32 inputlen, UINT8 flags = CHD_MDFLAGS_CHECKSUM);
  383      chd_error write_metadata(chd_metadata_tag metatag, UINT32 metaindex, const astring &input, UINT8 flags = CHD_MDFLAGS_CHECKSUM) { return write_metadata(metatag, metaindex, input.cstr(), input.len() + 1, flags); }
  384      chd_error write_metadata(chd_metadata_tag metatag, UINT32 metaindex, const dynamic_buffer &input, UINT8 flags = CHD_MDFLAGS_CHECKSUM) { return write_metadata(metatag, metaindex, input, input.count(), flags); }
  385      chd_error delete_metadata(chd_metadata_tag metatag, UINT32 metaindex);
  386      chd_error clone_all_metadata(chd_file &source);
  387  
  388      // hashing helper
  389      sha1_t compute_overall_sha1(sha1_t rawsha1);
  390  
  391      // codec interfaces
  392      chd_error codec_configure(chd_codec_type codec, int param, void *config);
  393  
  394      // static helpers
  395      static const char *error_string(chd_error err);
  396  
  397  private:
  398      struct metadata_entry;
  399      struct metadata_hash;
  400  
  401      // inline helpers
  402      UINT64 be_read(const UINT8 *base, int numbytes);
  403      void be_write(UINT8 *base, UINT64 value, int numbytes);
  404      sha1_t be_read_sha1(const UINT8 *base);
  405      void be_write_sha1(UINT8 *base, sha1_t value);
  406      void file_read(UINT64 offset, void *dest, UINT32 length);
  407      void file_write(UINT64 offset, const void *source, UINT32 length);
  408      UINT64 file_append(const void *source, UINT32 length, UINT32 alignment = 0);
  409      UINT8 bits_for_value(UINT64 value);
  410  
  411      // internal helpers
  412      UINT32 guess_unitbytes();
  413      void parse_v3_header(UINT8 *rawheader, sha1_t &parentsha1);
  414      void parse_v4_header(UINT8 *rawheader, sha1_t &parentsha1);
  415      void parse_v5_header(UINT8 *rawheader, sha1_t &parentsha1);
  416      chd_error compress_v5_map();
  417      void decompress_v5_map();
  418      chd_error create_common();
  419      chd_error open_common(bool writeable);
  420      void create_open_common();
  421      void verify_proper_compression_append(UINT32 hunknum);
  422      void hunk_write_compressed(UINT32 hunknum, INT8 compression, const UINT8 *compressed, UINT32 complength, crc16_t crc16);
  423      void hunk_copy_from_self(UINT32 hunknum, UINT32 otherhunk);
  424      void hunk_copy_from_parent(UINT32 hunknum, UINT64 parentunit);
  425      bool metadata_find(chd_metadata_tag metatag, INT32 metaindex, metadata_entry &metaentry, bool resume = false);
  426      void metadata_set_previous_next(UINT64 prevoffset, UINT64 nextoffset);
  427      void metadata_update_hash();
  428      static int CLIB_DECL metadata_hash_compare(const void *elem1, const void *elem2);
  429  
  430      // file characteristics
  431      core_file *             m_file;             // handle to the open core file
  432      bool                    m_owns_file;        // flag indicating if this file should be closed on chd_close()
  433      bool                    m_allow_reads;      // permit reads from this CHD?
  434      bool                    m_allow_writes;     // permit writes to this CHD?
  435  
  436      // core parameters from the header
  437      UINT32                  m_version;          // version of the header
  438      UINT64                  m_logicalbytes;     // logical size of the raw CHD data in bytes
  439      UINT64                  m_mapoffset;        // offset of map
  440      UINT64                  m_metaoffset;       // offset to first metadata bit
  441      UINT32                  m_hunkbytes;        // size of each raw hunk in bytes
  442      UINT32                  m_hunkcount;        // number of hunks represented
  443      UINT32                  m_unitbytes;        // size of each unit in bytes
  444      UINT64                  m_unitcount;        // number of units represented
  445      chd_codec_type          m_compression[4];   // array of compression types used
  446      chd_file *              m_parent;           // pointer to parent file, or NULL if none
  447      bool                    m_parent_missing;   // are we missing our parent?
  448  
  449      // key offsets within the header
  450      UINT64                  m_mapoffset_offset; // offset of map offset field
  451      UINT64                  m_metaoffset_offset;// offset of metaoffset field
  452      UINT64                  m_sha1_offset;      // offset of SHA1 field
  453      UINT64                  m_rawsha1_offset;   // offset of raw SHA1 field
  454      UINT64                  m_parentsha1_offset;// offset of paren SHA1 field
  455  
  456      // map information
  457      UINT32                  m_mapentrybytes;    // length of each entry in a map
  458      dynamic_buffer          m_rawmap;           // raw map data
  459  
  460      // compression management
  461      chd_decompressor *      m_decompressor[4];  // array of decompression codecs
  462      dynamic_buffer          m_compressed;       // temporary buffer for compressed data
  463  
  464      // caching
  465      dynamic_buffer          m_cache;            // single-hunk cache for partial reads/writes
  466      UINT32                  m_cachehunk;        // which hunk is in the cache?
  467  };
  468  
  469  
  470  // ======================> chd_file_compressor
  471  
  472  // class for creating a new compressed CHD
  473  class chd_file_compressor : public chd_file
  474  {
  475  public:
  476      // construction/destruction
  477      chd_file_compressor();
  478      virtual ~chd_file_compressor();
  479  
  480      // compression management
  481      void compress_begin();
  482      chd_error compress_continue(double &progress, double &ratio);
  483  
  484  protected:
  485      // required override: read more data
  486      virtual UINT32 read_data(void *dest, UINT64 offset, UINT32 length) = 0;
  487  
  488  private:
  489      // hash map for looking up values
  490      class hashmap
  491      {
  492      public:
  493          // construction/destruction
  494          hashmap();
  495          ~hashmap();
  496  
  497          // operations
  498          void reset();
  499          UINT64 find(crc16_t crc16, sha1_t sha1);
  500          void add(UINT64 itemnum, crc16_t crc16, sha1_t sha1);
  501  
  502          // constants
  503          static const UINT64 NOT_FOUND = ~UINT64(0);
  504      private:
  505          // internal entry
  506          struct entry_t
  507          {
  508              entry_t *           m_next;             // next entry in list
  509              UINT64              m_itemnum;          // item number
  510              sha1_t              m_sha1;             // SHA-1 of the block
  511          };
  512  
  513          // block of entries
  514          struct entry_block
  515          {
  516              entry_block(entry_block *prev)
  517                  : m_next(prev), m_nextalloc(0) { }
  518  
  519              entry_block *       m_next;             // next block in list
  520              UINT32              m_nextalloc;        // next to be allocated
  521              entry_t             m_array[16384];     // array of entries
  522          };
  523  
  524          // internal state
  525          entry_t *           m_map[65536];           // map, hashed by CRC-16
  526          entry_block *       m_block_list;           // list of allocated blocks
  527      };
  528  
  529      // status of a given work item
  530      enum work_status
  531      {
  532          WS_READY = 0,
  533          WS_READING,
  534          WS_QUEUED,
  535          WS_COMPLETE
  536      };
  537  
  538      // a CRC-16/SHA-1 pair
  539      struct hash_pair
  540      {
  541          crc16_t             m_crc16;            // calculated CRC-16
  542          sha1_t              m_sha1;             // calculated SHA-1
  543      };
  544  
  545      // a single work item
  546      struct work_item
  547      {
  548          osd_work_item *     m_osd;              // OSD work item running on this block
  549          chd_file_compressor *m_compressor;      // pointer back to the compressor
  550          volatile work_status m_status;          // current status of this item
  551          UINT32              m_hunknum;          // number of the hunk we're working on
  552          UINT8 *             m_data;             // pointer to the data we are working on
  553          UINT8 *             m_compressed;       // pointer to the compressed data
  554          UINT32              m_complen;          // compressed data length
  555          INT8                m_compression;      // type of compression used
  556          chd_compressor_group *m_codecs;         // codec instance
  557          dynamic_array<hash_pair> m_hash;        // array of hashes
  558      };
  559  
  560      // internal helpers
  561      static void *async_walk_parent_static(void *param, int threadid);
  562      void async_walk_parent(work_item &item);
  563      static void *async_compress_hunk_static(void *param, int threadid);
  564      void async_compress_hunk(work_item &item, int threadid);
  565      static void *async_read_static(void *param, int threadid);
  566      void async_read();
  567  
  568      // current compression status
  569      bool                    m_walking_parent;   // are we building the parent map?
  570      UINT64                  m_total_in;         // total bytes in
  571      UINT64                  m_total_out;        // total bytes out
  572      sha1_creator            m_compsha1;         // running SHA-1 on raw data
  573  
  574      // hash lookup maps
  575      hashmap                 m_parent_map;       // hash map for parent
  576      hashmap                 m_current_map;      // hash map for current
  577  
  578      // read I/O thread
  579      osd_work_queue *        m_read_queue;       // work queue for reading
  580      UINT64                  m_read_queue_offset;// next offset to enqueue
  581      UINT64                  m_read_done_offset; // next offset that will complete
  582      bool                    m_read_error;       // error during reading?
  583  
  584      // work item thread
  585      static const int WORK_BUFFER_HUNKS = 256;
  586      osd_work_queue *        m_work_queue;       // queue for doing work on other threads
  587      dynamic_buffer          m_work_buffer;      // buffer containing hunk data to work on
  588      dynamic_buffer          m_compressed_buffer;// buffer containing compressed data
  589      work_item               m_work_item[WORK_BUFFER_HUNKS]; // status of each hunk
  590      chd_compressor_group *  m_codecs[WORK_MAX_THREADS]; // codecs to use
  591  
  592      // output state
  593      UINT32                  m_write_hunk;       // next hunk to write
  594  };
  595  
  596  
  597  #endif // __CHD_H__