deps/libchdr/chd.c

   1 /***************************************************************************
   2
   3     chd.c
   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 #include <stddef.h>
  41 #include <stdio.h>
  42 #include <stdlib.h>
  43 #include <string.h>
  44 #include <time.h>
  45 #include "chd.h"
  46 #include "cdrom.h"
  47 #include "flac.h"
  48 #include "huffman.h"
  49 #include "LzmaEnc.h"
  50 #include "LzmaDec.h"
  51 #include "md5.h"
  52 #include "sha1.h"
  53 #include "zlib.h"
  54
  55 #define TRUE 1
  56 #define FALSE 0
  57
  58 #define MAX(x, y) (((x) > (y)) ? (x) : (y))
  59 #define MIN(x, y) (((x) < (y)) ? (x) : (y))
  60
  61 #define SHA1_DIGEST_SIZE 20
  62
  63 /***************************************************************************
  64     DEBUGGING
  65 ***************************************************************************/
  66
  67 #define PRINTF_MAX_HUNK                         (0)
  68
  69 /***************************************************************************
  70     CONSTANTS
  71 ***************************************************************************/
  72
  73 #define MAP_STACK_ENTRIES                       512                     /* max number of entries to use on the stack */
  74 #define MAP_ENTRY_SIZE                          16                      /* V3 and later */
  75 #define OLD_MAP_ENTRY_SIZE                      8                       /* V1-V2 */
  76 #define METADATA_HEADER_SIZE            16                      /* metadata header size */
  77 #define CRCMAP_HASH_SIZE                        4095            /* number of CRC hashtable entries */
  78
  79 #define MAP_ENTRY_FLAG_TYPE_MASK        0x0f            /* what type of hunk */
  80 #define MAP_ENTRY_FLAG_NO_CRC           0x10            /* no CRC is present */
  81
  82 #define CHD_V1_SECTOR_SIZE                      512                     /* size of a "sector" in the V1 header */
  83
  84 #define COOKIE_VALUE                            0xbaadf00d
  85 #define MAX_ZLIB_ALLOCS                         64
  86
  87 #define END_OF_LIST_COOKIE                      "EndOfListCookie"
  88
  89 #define NO_MATCH                                        (~0)
  90
  91 static const uint8_t s_cd_sync_header[12] = { 0x00,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0x00 };
  92
  93 /* V3-V4 entry types */
  94 enum
  95 {
  96         V34_MAP_ENTRY_TYPE_INVALID = 0,             /* invalid type */
  97         V34_MAP_ENTRY_TYPE_COMPRESSED = 1,          /* standard compression */
  98         V34_MAP_ENTRY_TYPE_UNCOMPRESSED = 2,        /* uncompressed data */
  99         V34_MAP_ENTRY_TYPE_MINI = 3,                /* mini: use offset as raw data */
 100         V34_MAP_ENTRY_TYPE_SELF_HUNK = 4,           /* same as another hunk in this file */
 101         V34_MAP_ENTRY_TYPE_PARENT_HUNK = 5,         /* same as a hunk in the parent file */
 102         V34_MAP_ENTRY_TYPE_2ND_COMPRESSED = 6       /* compressed with secondary algorithm (usually FLAC CDDA) */
 103 };
 104
 105 /* V5 compression types */
 106 enum
 107 {
 108         /* codec #0
 109          * these types are live when running */
 110         COMPRESSION_TYPE_0 = 0,
 111         /* codec #1 */
 112         COMPRESSION_TYPE_1 = 1,
 113         /* codec #2 */
 114         COMPRESSION_TYPE_2 = 2,
 115         /* codec #3 */
 116         COMPRESSION_TYPE_3 = 3,
 117         /* no compression; implicit length = hunkbytes */
 118         COMPRESSION_NONE = 4,
 119         /* same as another block in this chd */
 120         COMPRESSION_SELF = 5,
 121         /* same as a hunk's worth of units in the parent chd */
 122         COMPRESSION_PARENT = 6,
 123
 124         /* start of small RLE run (4-bit length)
 125          * these additional pseudo-types are used for compressed encodings: */
 126         COMPRESSION_RLE_SMALL,
 127         /* start of large RLE run (8-bit length) */
 128         COMPRESSION_RLE_LARGE,
 129         /* same as the last COMPRESSION_SELF block */
 130         COMPRESSION_SELF_0,
 131         /* same as the last COMPRESSION_SELF block + 1 */
 132         COMPRESSION_SELF_1,
 133         /* same block in the parent */
 134         COMPRESSION_PARENT_SELF,
 135         /* same as the last COMPRESSION_PARENT block */
 136         COMPRESSION_PARENT_0,
 137         /* same as the last COMPRESSION_PARENT block + 1 */
 138         COMPRESSION_PARENT_1
 139 };
 140
 141 /***************************************************************************
 142     MACROS
 143 ***************************************************************************/
 144
 145 #define EARLY_EXIT(x)                           do { (void)(x); goto cleanup; } while (0)
 146
 147 /***************************************************************************
 148     TYPE DEFINITIONS
 149 ***************************************************************************/
 150
 151 /* interface to a codec */
 152 typedef struct _codec_interface codec_interface;
 153 struct _codec_interface
 154 {
 155         UINT32          compression;                                                            /* type of compression */
 156         const char *compname;                                                                   /* name of the algorithm */
 157         UINT8           lossy;                                                                          /* is this a lossy algorithm? */
 158         chd_error       (*init)(void *codec, UINT32 hunkbytes);         /* codec initialize */
 159         void            (*free)(void *codec);                                           /* codec free */
 160         chd_error       (*decompress)(void *codec, const uint8_t *src, uint32_t complen, uint8_t *dest, uint32_t destlen); /* decompress data */
 161         chd_error       (*config)(void *codec, int param, void *config); /* configure */
 162 };
 163
 164 /* a single map entry */
 165 typedef struct _map_entry map_entry;
 166 struct _map_entry
 167 {
 168         UINT64                                  offset;                 /* offset within the file of the data */
 169         UINT32                                  crc;                    /* 32-bit CRC of the data */
 170         UINT32                                  length;                 /* length of the data */
 171         UINT8                                   flags;                  /* misc flags */
 172 };
 173
 174 /* simple linked-list of hunks used for our CRC map */
 175 typedef struct _crcmap_entry crcmap_entry;
 176 struct _crcmap_entry
 177 {
 178         UINT32                                  hunknum;                /* hunk number */
 179         crcmap_entry *                  next;                   /* next entry in list */
 180 };
 181
 182 /* a single metadata entry */
 183 typedef struct _metadata_entry metadata_entry;
 184 struct _metadata_entry
 185 {
 186         UINT64                                  offset;                 /* offset within the file of the header */
 187         UINT64                                  next;                   /* offset within the file of the next header */
 188         UINT64                                  prev;                   /* offset within the file of the previous header */
 189         UINT32                                  length;                 /* length of the metadata */
 190         UINT32                                  metatag;                /* metadata tag */
 191         UINT8                                   flags;                  /* flag bits */
 192 };
 193
 194 /* codec-private data for the ZLIB codec */
 195
 196 typedef struct _zlib_allocator zlib_allocator;
 197 struct _zlib_allocator
 198 {
 199         UINT32 *                                allocptr[MAX_ZLIB_ALLOCS];
 200         UINT32 *                                allocptr2[MAX_ZLIB_ALLOCS];
 201 };
 202
 203 typedef struct _zlib_codec_data zlib_codec_data;
 204 struct _zlib_codec_data
 205 {
 206         z_stream                                inflater;
 207         zlib_allocator                  allocator;
 208 };
 209
 210 /* codec-private data for the LZMA codec */
 211 #define MAX_LZMA_ALLOCS 64
 212
 213 typedef struct _lzma_allocator lzma_allocator;
 214 struct _lzma_allocator
 215 {
 216         void *(*Alloc)(void *p, size_t size);
 217         void (*Free)(void *p, void *address); /* address can be 0 */
 218         void (*FreeSz)(void *p, void *address, size_t size); /* address can be 0 */
 219         uint32_t*       allocptr[MAX_LZMA_ALLOCS];
 220         uint32_t*       allocptr2[MAX_LZMA_ALLOCS];
 221 };
 222
 223 typedef struct _lzma_codec_data lzma_codec_data;
 224 struct _lzma_codec_data
 225 {
 226         CLzmaDec                decoder;
 227         lzma_allocator  allocator;
 228 };
 229
 230 /* codec-private data for the CDZL codec */
 231 typedef struct _cdzl_codec_data cdzl_codec_data;
 232 struct _cdzl_codec_data {
 233         /* internal state */
 234         zlib_codec_data         base_decompressor;
 235         zlib_codec_data         subcode_decompressor;
 236         uint8_t*                        buffer;
 237 };
 238
 239 /* codec-private data for the CDLZ codec */
 240 typedef struct _cdlz_codec_data cdlz_codec_data;
 241 struct _cdlz_codec_data {
 242         /* internal state */
 243         lzma_codec_data         base_decompressor;
 244         zlib_codec_data         subcode_decompressor;
 245         uint8_t*                        buffer;
 246 };
 247
 248 /* codec-private data for the CDFL codec */
 249 typedef struct _cdfl_codec_data cdfl_codec_data;
 250 struct _cdfl_codec_data {
 251         /* internal state */
 252         int             swap_endian;
 253         flac_decoder    decoder;
 254         z_stream        inflater;
 255         zlib_allocator  allocator;
 256         uint8_t*        buffer;
 257 };
 258
 259 /* internal representation of an open CHD file */
 260 struct _chd_file
 261 {
 262         UINT32                                  cookie;                 /* cookie, should equal COOKIE_VALUE */
 263
 264         core_file *                             file;                   /* handle to the open core file */
 265         UINT8                                   owns_file;              /* flag indicating if this file should be closed on chd_close() */
 266         chd_header                              header;                 /* header, extracted from file */
 267
 268         chd_file *                              parent;                 /* pointer to parent file, or NULL */
 269
 270         map_entry *                             map;                    /* array of map entries */
 271
 272         UINT8 *                                 cache;                  /* hunk cache pointer */
 273         UINT32                                  cachehunk;              /* index of currently cached hunk */
 274
 275         UINT8 *                                 compare;                /* hunk compare pointer */
 276         UINT32                                  comparehunk;    /* index of current compare data */
 277
 278         UINT8 *                                 compressed;             /* pointer to buffer for compressed data */
 279         const codec_interface * codecintf[4];   /* interface to the codec */
 280
 281         zlib_codec_data                 zlib_codec_data;                /* zlib codec data */
 282         cdzl_codec_data                 cdzl_codec_data;                /* cdzl codec data */
 283         cdlz_codec_data                 cdlz_codec_data;                /* cdlz codec data */
 284         cdfl_codec_data                 cdfl_codec_data;                /* cdfl codec data */
 285
 286         crcmap_entry *                  crcmap;                 /* CRC map entries */
 287         crcmap_entry *                  crcfree;                /* free list CRC entries */
 288         crcmap_entry **                 crctable;               /* table of CRC entries */
 289
 290         UINT32                                  maxhunk;                /* maximum hunk accessed */
 291
 292         UINT8                                   compressing;    /* are we compressing? */
 293         MD5_CTX                                 compmd5;                /* running MD5 during compression */
 294         SHA1_CTX                                compsha1;               /* running SHA1 during compression */
 295         UINT32                                  comphunk;               /* next hunk we will compress */
 296
 297         UINT8                                   verifying;              /* are we verifying? */
 298         MD5_CTX                                 vermd5;                 /* running MD5 during verification */
 299         SHA1_CTX                                versha1;                /* running SHA1 during verification */
 300         UINT32                                  verhunk;                /* next hunk we will verify */
 301
 302         UINT32                                  async_hunknum;  /* hunk index for asynchronous operations */
 303         void *                                  async_buffer;   /* buffer pointer for asynchronous operations */
 304
 305         UINT8 *                                 file_cache;             /* cache of underlying file */
 306 };
 307
 308 /* a single metadata hash entry */
 309 typedef struct _metadata_hash metadata_hash;
 310 struct _metadata_hash
 311 {
 312         UINT8                                   tag[4];                 /* tag of the metadata in big-endian */
 313         UINT8                                   sha1[CHD_SHA1_BYTES]; /* hash */
 314 };
 315
 316 /***************************************************************************
 317     GLOBAL VARIABLES
 318 ***************************************************************************/
 319
 320 static const UINT8 nullmd5[CHD_MD5_BYTES] = { 0 };
 321 static const UINT8 nullsha1[CHD_SHA1_BYTES] = { 0 };
 322
 323 /***************************************************************************
 324     PROTOTYPES
 325 ***************************************************************************/
 326
 327 /* internal header operations */
 328 static chd_error header_validate(const chd_header *header);
 329 static chd_error header_read(chd_file *chd, chd_header *header);
 330
 331 /* internal hunk read/write */
 332 static chd_error hunk_read_into_cache(chd_file *chd, UINT32 hunknum);
 333 static chd_error hunk_read_into_memory(chd_file *chd, UINT32 hunknum, UINT8 *dest);
 334
 335 /* internal map access */
 336 static chd_error map_read(chd_file *chd);
 337
 338 /* metadata management */
 339 static chd_error metadata_find_entry(chd_file *chd, UINT32 metatag, UINT32 metaindex, metadata_entry *metaentry);
 340
 341 /* zlib compression codec */
 342 static chd_error zlib_codec_init(void *codec, uint32_t hunkbytes);
 343 static void zlib_codec_free(void *codec);
 344 static chd_error zlib_codec_decompress(void *codec, const uint8_t *src, uint32_t complen, uint8_t *dest, uint32_t destlen);
 345 static voidpf zlib_fast_alloc(voidpf opaque, uInt items, uInt size);
 346 static void zlib_fast_free(voidpf opaque, voidpf address);
 347 static void zlib_allocator_free(voidpf opaque);
 348
 349 /* lzma compression codec */
 350 static chd_error lzma_codec_init(void *codec, uint32_t hunkbytes);
 351 static void lzma_codec_free(void *codec);
 352 static chd_error lzma_codec_decompress(void *codec, const uint8_t *src, uint32_t complen, uint8_t *dest, uint32_t destlen);
 353
 354 /* cdzl compression codec */
 355 static chd_error cdzl_codec_init(void* codec, uint32_t hunkbytes);
 356 static void cdzl_codec_free(void* codec);
 357 static chd_error cdzl_codec_decompress(void *codec, const uint8_t *src, uint32_t complen, uint8_t *dest, uint32_t destlen);
 358
 359 /* cdlz compression codec */
 360 static chd_error cdlz_codec_init(void* codec, uint32_t hunkbytes);
 361 static void cdlz_codec_free(void* codec);
 362 static chd_error cdlz_codec_decompress(void *codec, const uint8_t *src, uint32_t complen, uint8_t *dest, uint32_t destlen);
 363
 364 /* cdfl compression codec */
 365 static chd_error cdfl_codec_init(void* codec, uint32_t hunkbytes);
 366 static void cdfl_codec_free(void* codec);
 367 static chd_error cdfl_codec_decompress(void *codec, const uint8_t *src, uint32_t complen, uint8_t *dest, uint32_t destlen);
 368
 369 /***************************************************************************
 370  *  LZMA ALLOCATOR HELPER
 371  ***************************************************************************
 372  */
 373
 374 void *lzma_fast_alloc(void *p, size_t size);
 375 void lzma_fast_free(void *p, void *address);
 376
 377 /*-------------------------------------------------
 378  *  lzma_allocator_init
 379  *-------------------------------------------------
 380  */
 381
 382 void lzma_allocator_init(void* p)
 383 {
 384         lzma_allocator *codec = (lzma_allocator *)(p);
 385
 386         /* reset pointer list */
 387         memset(codec->allocptr, 0, sizeof(codec->allocptr));
 388         memset(codec->allocptr2, 0, sizeof(codec->allocptr2));
 389         codec->Alloc = lzma_fast_alloc;
 390         codec->Free = lzma_fast_free;
 391 }
 392
 393 /*-------------------------------------------------
 394  *  lzma_allocator_free
 395  *-------------------------------------------------
 396  */
 397
 398 void lzma_allocator_free(void* p )
 399 {
 400         int i;
 401         lzma_allocator *codec = (lzma_allocator *)(p);
 402
 403         /* free our memory */
 404         for (i = 0 ; i < MAX_LZMA_ALLOCS ; i++)
 405         {
 406                 if (codec->allocptr[i] != NULL)
 407                         free(codec->allocptr[i]);
 408         }
 409 }
 410
 411 /*-------------------------------------------------
 412  *  lzma_fast_alloc - fast malloc for lzma, which
 413  *  allocates and frees memory frequently
 414  *-------------------------------------------------
 415  */
 416
 417 #define LZMA_MIN_ALIGNMENT_BITS 512
 418 #define LZMA_MIN_ALIGNMENT_BYTES (LZMA_MIN_ALIGNMENT_BITS / 8)
 419 void *lzma_fast_alloc(void *p, size_t size)
 420 {
 421         int scan;
 422         uint32_t *addr        = NULL;
 423         lzma_allocator *codec = (lzma_allocator *)(p);
 424
 425         uintptr_t vaddr = 0;
 426
 427         /* compute the size, rounding to the nearest 1k */
 428         size = (size + 0x3ff) & ~0x3ff;
 429
 430         /* reuse a hunk if we can */
 431         for (scan = 0; scan < MAX_LZMA_ALLOCS; scan++)
 432         {
 433                 uint32_t *ptr = codec->allocptr[scan];
 434                 if (ptr != NULL && size == *ptr)
 435                 {
 436                         /* set the low bit of the size so we don't match next time */
 437                         *ptr |= 1;
 438                         return codec->allocptr2[scan];
 439                 }
 440         }
 441
 442         /* alloc a new one and put it into the list */
 443         addr = (uint32_t *)malloc(size + sizeof(uint32_t) + LZMA_MIN_ALIGNMENT_BYTES);
 444         if (addr==NULL)
 445                 return NULL;
 446         for (int scan = 0; scan < MAX_LZMA_ALLOCS; scan++)
 447         {
 448                 if (codec->allocptr[scan] == NULL)
 449                 {
 450                         codec->allocptr[scan] = addr;
 451                         vaddr = (uintptr_t)addr;
 452                         vaddr = (vaddr + sizeof(uint32_t) + (LZMA_MIN_ALIGNMENT_BYTES-1)) & (~(LZMA_MIN_ALIGNMENT_BYTES-1));
 453                         codec->allocptr2[scan] = (uint32_t*)vaddr;
 454                         break;
 455                 }
 456         }
 457
 458         /* set the low bit of the size so we don't match next time */
 459         *addr = size | 1;
 460         return (void*)vaddr;
 461 }
 462
 463 /*-------------------------------------------------
 464  *  lzma_fast_free - fast free for lzma, which
 465  *  allocates and frees memory frequently
 466  *-------------------------------------------------
 467  */
 468
 469 void lzma_fast_free(void *p, void *address)
 470 {
 471         int scan;
 472         uint32_t *ptr = NULL;
 473         lzma_allocator *codec = NULL;
 474
 475         if (address == NULL)
 476                 return;
 477
 478         codec = (lzma_allocator *)(p);
 479
 480         /* find the hunk */
 481         ptr = (uint32_t *)address;
 482         for (scan = 0; scan < MAX_LZMA_ALLOCS; scan++)
 483         {
 484                 if (ptr == codec->allocptr2[scan])
 485                 {
 486                         /* clear the low bit of the size to allow matches */
 487                         *codec->allocptr[scan] &= ~1;
 488                         return;
 489                 }
 490         }
 491 }
 492
 493 /***************************************************************************
 494  *  LZMA DECOMPRESSOR
 495  ***************************************************************************
 496  */
 497
 498 /*-------------------------------------------------
 499  *  lzma_codec_init - constructor
 500  *-------------------------------------------------
 501  */
 502
 503 chd_error lzma_codec_init(void* codec, uint32_t hunkbytes)
 504 {
 505         CLzmaEncHandle enc;
 506         CLzmaEncProps encoder_props;
 507         Byte decoder_props[LZMA_PROPS_SIZE];
 508         SizeT props_size;
 509         lzma_allocator* alloc;
 510         lzma_codec_data* lzma_codec = (lzma_codec_data*) codec;
 511
 512         /* construct the decoder */
 513         LzmaDec_Construct(&lzma_codec->decoder);
 514
 515         /* FIXME: this code is written in a way that makes it impossible to safely upgrade the LZMA SDK
 516          * This code assumes that the current version of the encoder imposes the same requirements on the
 517          * decoder as the encoder used to produce the file.  This is not necessarily true.  The format
 518          * needs to be changed so the encoder properties are written to the file.
 519
 520          * configure the properties like the compressor did */
 521         LzmaEncProps_Init(&encoder_props);
 522         encoder_props.level = 9;
 523         encoder_props.reduceSize = hunkbytes;
 524         LzmaEncProps_Normalize(&encoder_props);
 525
 526         /* convert to decoder properties */
 527         alloc = &lzma_codec->allocator;
 528         lzma_allocator_init(alloc);
 529         enc = LzmaEnc_Create((ISzAlloc*)alloc);
 530         if (!enc)
 531                 return CHDERR_DECOMPRESSION_ERROR;
 532         if (LzmaEnc_SetProps(enc, &encoder_props) != SZ_OK)
 533         {
 534                 LzmaEnc_Destroy(enc, (ISzAlloc*)&alloc, (ISzAlloc*)&alloc);
 535                 return CHDERR_DECOMPRESSION_ERROR;
 536         }
 537         props_size = sizeof(decoder_props);
 538         if (LzmaEnc_WriteProperties(enc, decoder_props, &props_size) != SZ_OK)
 539         {
 540                 LzmaEnc_Destroy(enc, (ISzAlloc*)alloc, (ISzAlloc*)alloc);
 541                 return CHDERR_DECOMPRESSION_ERROR;
 542         }
 543         LzmaEnc_Destroy(enc, (ISzAlloc*)alloc, (ISzAlloc*)alloc);
 544
 545         /* do memory allocations */
 546         if (LzmaDec_Allocate(&lzma_codec->decoder, decoder_props, LZMA_PROPS_SIZE, (ISzAlloc*)alloc) != SZ_OK)
 547                 return CHDERR_DECOMPRESSION_ERROR;
 548
 549         /* Okay */
 550         return CHDERR_NONE;
 551 }
 552
 553 /*-------------------------------------------------
 554  *  lzma_codec_free
 555  *-------------------------------------------------
 556  */
 557
 558 void lzma_codec_free(void* codec)
 559 {
 560         lzma_codec_data* lzma_codec = (lzma_codec_data*) codec;
 561
 562         /* free memory */
 563         LzmaDec_Free(&lzma_codec->decoder, (ISzAlloc*)&lzma_codec->allocator);
 564         lzma_allocator_free(&lzma_codec->allocator);
 565 }
 566
 567 /*-------------------------------------------------
 568  *  decompress - decompress data using the LZMA
 569  *  codec
 570  *-------------------------------------------------
 571  */
 572
 573 chd_error lzma_codec_decompress(void* codec, const uint8_t *src, uint32_t complen, uint8_t *dest, uint32_t destlen)
 574 {
 575         ELzmaStatus status;
 576         SRes res;
 577         SizeT consumedlen, decodedlen;
 578         /* initialize */
 579         lzma_codec_data* lzma_codec = (lzma_codec_data*) codec;
 580         LzmaDec_Init(&lzma_codec->decoder);
 581
 582         /* decode */
 583         consumedlen = complen;
 584         decodedlen = destlen;
 585         res = LzmaDec_DecodeToBuf(&lzma_codec->decoder, dest, &decodedlen, src, &consumedlen, LZMA_FINISH_END, &status);
 586         if ((res != SZ_OK && res != LZMA_STATUS_MAYBE_FINISHED_WITHOUT_MARK) || consumedlen != complen || decodedlen != destlen)
 587                 return CHDERR_DECOMPRESSION_ERROR;
 588         return CHDERR_NONE;
 589 }
 590
 591 /* cdlz */
 592 chd_error cdlz_codec_init(void* codec, uint32_t hunkbytes)
 593 {
 594         cdlz_codec_data* cdlz = (cdlz_codec_data*) codec;
 595
 596         /* allocate buffer */
 597         cdlz->buffer = (uint8_t*)malloc(sizeof(uint8_t) * hunkbytes);
 598
 599         /* make sure the CHD's hunk size is an even multiple of the frame size */
 600         lzma_codec_init(&cdlz->base_decompressor, (hunkbytes / CD_FRAME_SIZE) * CD_MAX_SECTOR_DATA);
 601         zlib_codec_init(&cdlz->subcode_decompressor, (hunkbytes / CD_FRAME_SIZE) * CD_MAX_SUBCODE_DATA);
 602
 603         if (hunkbytes % CD_FRAME_SIZE != 0)
 604                 return CHDERR_CODEC_ERROR;
 605
 606         return CHDERR_NONE;
 607 }
 608
 609 void cdlz_codec_free(void* codec)
 610 {
 611         cdlz_codec_data* cdlz = (cdlz_codec_data*) codec;
 612         free(cdlz->buffer);
 613         lzma_codec_free(&cdlz->base_decompressor);
 614         zlib_codec_free(&cdlz->subcode_decompressor);
 615 }
 616
 617 chd_error cdlz_codec_decompress(void *codec, const uint8_t *src, uint32_t complen, uint8_t *dest, uint32_t destlen)
 618 {
 619         uint32_t framenum;
 620         cdlz_codec_data* cdlz = (cdlz_codec_data*)codec;
 621
 622         /* determine header bytes */
 623         uint32_t frames = destlen / CD_FRAME_SIZE;
 624         uint32_t complen_bytes = (destlen < 65536) ? 2 : 3;
 625         uint32_t ecc_bytes = (frames + 7) / 8;
 626         uint32_t header_bytes = ecc_bytes + complen_bytes;
 627
 628         /* extract compressed length of base */
 629         uint32_t complen_base = (src[ecc_bytes + 0] << 8) | src[ecc_bytes + 1];
 630         if (complen_bytes > 2)
 631                 complen_base = (complen_base << 8) | src[ecc_bytes + 2];
 632
 633         /* reset and decode */
 634         lzma_codec_decompress(&cdlz->base_decompressor, &src[header_bytes], complen_base, &cdlz->buffer[0], frames * CD_MAX_SECTOR_DATA);
 635         zlib_codec_decompress(&cdlz->subcode_decompressor, &src[header_bytes + complen_base], complen - complen_base - header_bytes, &cdlz->buffer[frames * CD_MAX_SECTOR_DATA], frames * CD_MAX_SUBCODE_DATA);
 636
 637         /* reassemble the data */
 638         for (framenum = 0; framenum < frames; framenum++)
 639         {
 640                 uint8_t *sector;
 641
 642                 memcpy(&dest[framenum * CD_FRAME_SIZE], &cdlz->buffer[framenum * CD_MAX_SECTOR_DATA], CD_MAX_SECTOR_DATA);
 643                 memcpy(&dest[framenum * CD_FRAME_SIZE + CD_MAX_SECTOR_DATA], &cdlz->buffer[frames * CD_MAX_SECTOR_DATA + framenum * CD_MAX_SUBCODE_DATA], CD_MAX_SUBCODE_DATA);
 644
 645                 /* reconstitute the ECC data and sync header */
 646                 sector = (uint8_t *)&dest[framenum * CD_FRAME_SIZE];
 647                 if ((src[framenum / 8] & (1 << (framenum % 8))) != 0)
 648                 {
 649                         memcpy(sector, s_cd_sync_header, sizeof(s_cd_sync_header));
 650                         ecc_generate(sector);
 651                 }
 652         }
 653         return CHDERR_NONE;
 654 }
 655
 656 /* cdzl */
 657
 658 chd_error cdzl_codec_init(void *codec, uint32_t hunkbytes)
 659 {
 660         cdzl_codec_data* cdzl = (cdzl_codec_data*)codec;
 661
 662         /* make sure the CHD's hunk size is an even multiple of the frame size */
 663         zlib_codec_init(&cdzl->base_decompressor, (hunkbytes / CD_FRAME_SIZE) * CD_MAX_SECTOR_DATA);
 664         zlib_codec_init(&cdzl->subcode_decompressor, (hunkbytes / CD_FRAME_SIZE) * CD_MAX_SUBCODE_DATA);
 665
 666         cdzl->buffer = (uint8_t*)malloc(sizeof(uint8_t) * hunkbytes);
 667         if (hunkbytes % CD_FRAME_SIZE != 0)
 668                 return CHDERR_CODEC_ERROR;
 669
 670         return CHDERR_NONE;
 671 }
 672
 673 void cdzl_codec_free(void *codec)
 674 {
 675         cdzl_codec_data* cdzl = (cdzl_codec_data*)codec;
 676         zlib_codec_free(&cdzl->base_decompressor);
 677         zlib_codec_free(&cdzl->subcode_decompressor);
 678         free(cdzl->buffer);
 679 }
 680
 681 chd_error cdzl_codec_decompress(void *codec, const uint8_t *src, uint32_t complen, uint8_t *dest, uint32_t destlen)
 682 {
 683         uint32_t framenum;
 684         cdzl_codec_data* cdzl = (cdzl_codec_data*)codec;
 685
 686         /* determine header bytes */
 687         uint32_t frames = destlen / CD_FRAME_SIZE;
 688         uint32_t complen_bytes = (destlen < 65536) ? 2 : 3;
 689         uint32_t ecc_bytes = (frames + 7) / 8;
 690         uint32_t header_bytes = ecc_bytes + complen_bytes;
 691
 692         /* extract compressed length of base */
 693         uint32_t complen_base = (src[ecc_bytes + 0] << 8) | src[ecc_bytes + 1];
 694         if (complen_bytes > 2)
 695                 complen_base = (complen_base << 8) | src[ecc_bytes + 2];
 696
 697         /* reset and decode */
 698         zlib_codec_decompress(&cdzl->base_decompressor, &src[header_bytes], complen_base, &cdzl->buffer[0], frames * CD_MAX_SECTOR_DATA);
 699         zlib_codec_decompress(&cdzl->subcode_decompressor, &src[header_bytes + complen_base], complen - complen_base - header_bytes, &cdzl->buffer[frames * CD_MAX_SECTOR_DATA], frames * CD_MAX_SUBCODE_DATA);
 700
 701         /* reassemble the data */
 702         for (framenum = 0; framenum < frames; framenum++)
 703         {
 704                 uint8_t *sector;
 705
 706                 memcpy(&dest[framenum * CD_FRAME_SIZE], &cdzl->buffer[framenum * CD_MAX_SECTOR_DATA], CD_MAX_SECTOR_DATA);
 707                 memcpy(&dest[framenum * CD_FRAME_SIZE + CD_MAX_SECTOR_DATA], &cdzl->buffer[frames * CD_MAX_SECTOR_DATA + framenum * CD_MAX_SUBCODE_DATA], CD_MAX_SUBCODE_DATA);
 708
 709                 /* reconstitute the ECC data and sync header */
 710                 sector = (uint8_t *)&dest[framenum * CD_FRAME_SIZE];
 711                 if ((src[framenum / 8] & (1 << (framenum % 8))) != 0)
 712                 {
 713                         memcpy(sector, s_cd_sync_header, sizeof(s_cd_sync_header));
 714                         ecc_generate(sector);
 715                 }
 716         }
 717         return CHDERR_NONE;
 718 }
 719
 720 /***************************************************************************
 721  *  CD FLAC DECOMPRESSOR
 722  ***************************************************************************
 723  */
 724
 725 /*------------------------------------------------------
 726  *  cdfl_codec_blocksize - return the optimal block size
 727  *------------------------------------------------------
 728  */
 729
 730 static uint32_t cdfl_codec_blocksize(uint32_t bytes)
 731 {
 732         /* determine FLAC block size, which must be 16-65535
 733          * clamp to 2k since that's supposed to be the sweet spot */
 734         uint32_t hunkbytes = bytes / 4;
 735         while (hunkbytes > 2048)
 736                 hunkbytes /= 2;
 737         return hunkbytes;
 738 }
 739
 740 chd_error cdfl_codec_init(void *codec, uint32_t hunkbytes)
 741 {
 742         int zerr;
 743         uint16_t native_endian = 0;
 744         cdfl_codec_data *cdfl = (cdfl_codec_data*)codec;
 745
 746         cdfl->buffer = (uint8_t*)malloc(sizeof(uint8_t) * hunkbytes);
 747
 748         /* make sure the CHD's hunk size is an even multiple of the frame size */
 749         if (hunkbytes % CD_FRAME_SIZE != 0)
 750                 return CHDERR_CODEC_ERROR;
 751
 752         /* determine whether we want native or swapped samples */
 753         *(uint8_t *)(&native_endian) = 1;
 754         cdfl->swap_endian = (native_endian & 1);
 755
 756         /* init the inflater */
 757         cdfl->inflater.next_in = (Bytef *)cdfl; /* bogus, but that's ok */
 758         cdfl->inflater.avail_in = 0;
 759 #if 0
 760         cdfl->allocator.install(cdfl->inflater);
 761 #endif
 762         cdfl->inflater.zalloc = zlib_fast_alloc;
 763         cdfl->inflater.zfree = zlib_fast_free;
 764         cdfl->inflater.opaque = &cdfl->allocator;
 765         zerr = inflateInit2(&cdfl->inflater, -MAX_WBITS);
 766
 767         /* convert errors */
 768         if (zerr == Z_MEM_ERROR)
 769                 return CHDERR_OUT_OF_MEMORY;
 770         else if (zerr != Z_OK)
 771                 return CHDERR_CODEC_ERROR;
 772
 773         /* flac decoder init */
 774         flac_decoder_init(&cdfl->decoder);
 775         return CHDERR_NONE;
 776 }
 777
 778 void cdfl_codec_free(void *codec)
 779 {
 780         cdfl_codec_data *cdfl = (cdfl_codec_data*)codec;
 781         free(cdfl->buffer);
 782         inflateEnd(&cdfl->inflater);
 783         flac_decoder_free(&cdfl->decoder);
 784
 785         /* free our fast memory */
 786         zlib_allocator_free(&cdfl->allocator);
 787 }
 788
 789 chd_error cdfl_codec_decompress(void *codec, const uint8_t *src, uint32_t complen, uint8_t *dest, uint32_t destlen)
 790 {
 791         int zerr;
 792         uint8_t *buffer;
 793         uint32_t framenum, offset;
 794         cdfl_codec_data *cdfl = (cdfl_codec_data*)codec;
 795
 796         /* reset and decode */
 797         uint32_t frames = destlen / CD_FRAME_SIZE;
 798
 799         if (!flac_decoder_reset(&cdfl->decoder, 44100, 2, cdfl_codec_blocksize(frames * CD_MAX_SECTOR_DATA), src, complen))
 800                 return CHDERR_DECOMPRESSION_ERROR;
 801         buffer = &cdfl->buffer[0];
 802         if (!flac_decoder_decode_interleaved(&cdfl->decoder, (int16_t *)(buffer), frames * CD_MAX_SECTOR_DATA/4, cdfl->swap_endian))
 803                 return CHDERR_DECOMPRESSION_ERROR;
 804
 805         /* inflate the subcode data */
 806         offset = flac_decoder_finish(&cdfl->decoder);
 807         cdfl->inflater.next_in = (Bytef *)(src + offset);
 808         cdfl->inflater.avail_in = complen - offset;
 809         cdfl->inflater.total_in = 0;
 810         cdfl->inflater.next_out = &cdfl->buffer[frames * CD_MAX_SECTOR_DATA];
 811         cdfl->inflater.avail_out = frames * CD_MAX_SUBCODE_DATA;
 812         cdfl->inflater.total_out = 0;
 813         zerr = inflateReset(&cdfl->inflater);
 814         if (zerr != Z_OK)
 815                 return CHDERR_DECOMPRESSION_ERROR;
 816
 817         /* do it */
 818         zerr = inflate(&cdfl->inflater, Z_FINISH);
 819         if (zerr != Z_STREAM_END)
 820                 return CHDERR_DECOMPRESSION_ERROR;
 821         if (cdfl->inflater.total_out != frames * CD_MAX_SUBCODE_DATA)
 822                 return CHDERR_DECOMPRESSION_ERROR;
 823
 824         /* reassemble the data */
 825         for (framenum = 0; framenum < frames; framenum++)
 826         {
 827                 memcpy(&dest[framenum * CD_FRAME_SIZE], &cdfl->buffer[framenum * CD_MAX_SECTOR_DATA], CD_MAX_SECTOR_DATA);
 828                 memcpy(&dest[framenum * CD_FRAME_SIZE + CD_MAX_SECTOR_DATA], &cdfl->buffer[frames * CD_MAX_SECTOR_DATA + framenum * CD_MAX_SUBCODE_DATA], CD_MAX_SUBCODE_DATA);
 829         }
 830
 831         return CHDERR_NONE;
 832 }
 833 /***************************************************************************
 834     CODEC INTERFACES
 835 ***************************************************************************/
 836
 837 static const codec_interface codec_interfaces[] =
 838 {
 839         /* "none" or no compression */
 840         {
 841                 CHDCOMPRESSION_NONE,
 842                 "none",
 843                 FALSE,
 844                 NULL,
 845                 NULL,
 846                 NULL,
 847                 NULL
 848         },
 849
 850         /* standard zlib compression */
 851         {
 852                 CHDCOMPRESSION_ZLIB,
 853                 "zlib",
 854                 FALSE,
 855                 zlib_codec_init,
 856                 zlib_codec_free,
 857                 zlib_codec_decompress,
 858                 NULL
 859         },
 860
 861         /* zlib+ compression */
 862         {
 863                 CHDCOMPRESSION_ZLIB_PLUS,
 864                 "zlib+",
 865                 FALSE,
 866                 zlib_codec_init,
 867                 zlib_codec_free,
 868                 zlib_codec_decompress,
 869                 NULL
 870         },
 871
 872         /* V5 zlib compression */
 873         {
 874                 CHD_CODEC_ZLIB,
 875                 "zlib (Deflate)",
 876                 FALSE,
 877                 zlib_codec_init,
 878                 zlib_codec_free,
 879                 zlib_codec_decompress,
 880                 NULL
 881         },
 882
 883         /* V5 CD zlib compression */
 884         {
 885                 CHD_CODEC_CD_ZLIB,
 886                 "cdzl (CD Deflate)",
 887                 FALSE,
 888                 cdzl_codec_init,
 889                 cdzl_codec_free,
 890                 cdzl_codec_decompress,
 891                 NULL
 892         },
 893
 894         /* V5 CD lzma compression */
 895         {
 896                 CHD_CODEC_CD_LZMA,
 897                 "cdlz (CD LZMA)",
 898                 FALSE,
 899                 cdlz_codec_init,
 900                 cdlz_codec_free,
 901                 cdlz_codec_decompress,
 902                 NULL
 903         },
 904
 905         /* V5 CD flac compression */
 906         {
 907                 CHD_CODEC_CD_FLAC,
 908                 "cdfl (CD FLAC)",
 909                 FALSE,
 910                 cdfl_codec_init,
 911                 cdfl_codec_free,
 912                 cdfl_codec_decompress,
 913                 NULL
 914         },
 915 };
 916
 917 /***************************************************************************
 918     INLINE FUNCTIONS
 919 ***************************************************************************/
 920
 921 /*-------------------------------------------------
 922     get_bigendian_uint64 - fetch a UINT64 from
 923     the data stream in bigendian order
 924 -------------------------------------------------*/
 925
 926 static inline UINT64 get_bigendian_uint64(const UINT8 *base)
 927 {
 928         return ((UINT64)base[0] << 56) | ((UINT64)base[1] << 48) | ((UINT64)base[2] << 40) | ((UINT64)base[3] << 32) |
 929                         ((UINT64)base[4] << 24) | ((UINT64)base[5] << 16) | ((UINT64)base[6] << 8) | (UINT64)base[7];
 930 }
 931
 932 /*-------------------------------------------------
 933     put_bigendian_uint64 - write a UINT64 to
 934     the data stream in bigendian order
 935 -------------------------------------------------*/
 936
 937 static inline void put_bigendian_uint64(UINT8 *base, UINT64 value)
 938 {
 939         base[0] = value >> 56;
 940         base[1] = value >> 48;
 941         base[2] = value >> 40;
 942         base[3] = value >> 32;
 943         base[4] = value >> 24;
 944         base[5] = value >> 16;
 945         base[6] = value >> 8;
 946         base[7] = value;
 947 }
 948
 949 /*-------------------------------------------------
 950     get_bigendian_uint48 - fetch a UINT48 from
 951     the data stream in bigendian order
 952 -------------------------------------------------*/
 953
 954 static inline UINT64 get_bigendian_uint48(const UINT8 *base)
 955 {
 956         return  ((UINT64)base[0] << 40) | ((UINT64)base[1] << 32) |
 957                         ((UINT64)base[2] << 24) | ((UINT64)base[3] << 16) | ((UINT64)base[4] << 8) | (UINT64)base[5];
 958 }
 959
 960 /*-------------------------------------------------
 961     put_bigendian_uint48 - write a UINT48 to
 962     the data stream in bigendian order
 963 -------------------------------------------------*/
 964
 965 static inline void put_bigendian_uint48(UINT8 *base, UINT64 value)
 966 {
 967         value &= 0xffffffffffff;
 968         base[0] = value >> 40;
 969         base[1] = value >> 32;
 970         base[2] = value >> 24;
 971         base[3] = value >> 16;
 972         base[4] = value >> 8;
 973         base[5] = value;
 974 }
 975 /*-------------------------------------------------
 976     get_bigendian_uint32 - fetch a UINT32 from
 977     the data stream in bigendian order
 978 -------------------------------------------------*/
 979
 980 static inline UINT32 get_bigendian_uint32(const UINT8 *base)
 981 {
 982         return (base[0] << 24) | (base[1] << 16) | (base[2] << 8) | base[3];
 983 }
 984
 985 /*-------------------------------------------------
 986     put_bigendian_uint32 - write a UINT32 to
 987     the data stream in bigendian order
 988 -------------------------------------------------*/
 989
 990 static inline void put_bigendian_uint32(UINT8 *base, UINT32 value)
 991 {
 992         base[0] = value >> 24;
 993         base[1] = value >> 16;
 994         base[2] = value >> 8;
 995         base[3] = value;
 996 }
 997
 998 /*-------------------------------------------------
 999     put_bigendian_uint24 - write a UINT24 to
1000     the data stream in bigendian order
1001 -------------------------------------------------*/
1002
1003 static inline void put_bigendian_uint24(UINT8 *base, UINT32 value)
1004 {
1005         value &= 0xffffff;
1006         base[0] = value >> 16;
1007         base[1] = value >> 8;
1008         base[2] = value;
1009 }
1010
1011 /*-------------------------------------------------
1012     get_bigendian_uint24 - fetch a UINT24 from
1013     the data stream in bigendian order
1014 -------------------------------------------------*/
1015
1016 static inline UINT32 get_bigendian_uint24(const UINT8 *base)
1017 {
1018         return (base[0] << 16) | (base[1] << 8) | base[2];
1019 }
1020
1021 /*-------------------------------------------------
1022     get_bigendian_uint16 - fetch a UINT16 from
1023     the data stream in bigendian order
1024 -------------------------------------------------*/
1025
1026 static inline UINT16 get_bigendian_uint16(const UINT8 *base)
1027 {
1028         return (base[0] << 8) | base[1];
1029 }
1030
1031 /*-------------------------------------------------
1032     put_bigendian_uint16 - write a UINT16 to
1033     the data stream in bigendian order
1034 -------------------------------------------------*/
1035
1036 static inline void put_bigendian_uint16(UINT8 *base, UINT16 value)
1037 {
1038         base[0] = value >> 8;
1039         base[1] = value;
1040 }
1041
1042 /*-------------------------------------------------
1043     map_extract - extract a single map
1044     entry from the datastream
1045 -------------------------------------------------*/
1046
1047 static inline void map_extract(const UINT8 *base, map_entry *entry)
1048 {
1049         entry->offset = get_bigendian_uint64(&base[0]);
1050         entry->crc = get_bigendian_uint32(&base[8]);
1051         entry->length = get_bigendian_uint16(&base[12]) | (base[14] << 16);
1052         entry->flags = base[15];
1053 }
1054
1055 /*-------------------------------------------------
1056     map_assemble - write a single map
1057     entry to the datastream
1058 -------------------------------------------------*/
1059
1060 static inline void map_assemble(UINT8 *base, map_entry *entry)
1061 {
1062         put_bigendian_uint64(&base[0], entry->offset);
1063         put_bigendian_uint32(&base[8], entry->crc);
1064         put_bigendian_uint16(&base[12], entry->length);
1065         base[14] = entry->length >> 16;
1066         base[15] = entry->flags;
1067 }
1068
1069 /*-------------------------------------------------
1070     map_size_v5 - calculate CHDv5 map size
1071 -------------------------------------------------*/
1072 static inline int map_size_v5(chd_header* header)
1073 {
1074         return header->hunkcount * header->mapentrybytes;
1075 }
1076
1077 /*-------------------------------------------------
1078     crc16 - calculate CRC16 (from hashing.cpp)
1079 -------------------------------------------------*/
1080 uint16_t crc16(const void *data, uint32_t length)
1081 {
1082         uint16_t crc = 0xffff;
1083
1084         static const uint16_t s_table[256] =
1085         {
1086                 0x0000, 0x1021, 0x2042, 0x3063, 0x4084, 0x50a5, 0x60c6, 0x70e7,
1087                 0x8108, 0x9129, 0xa14a, 0xb16b, 0xc18c, 0xd1ad, 0xe1ce, 0xf1ef,
1088                 0x1231, 0x0210, 0x3273, 0x2252, 0x52b5, 0x4294, 0x72f7, 0x62d6,
1089                 0x9339, 0x8318, 0xb37b, 0xa35a, 0xd3bd, 0xc39c, 0xf3ff, 0xe3de,
1090                 0x2462, 0x3443, 0x0420, 0x1401, 0x64e6, 0x74c7, 0x44a4, 0x5485,
1091                 0xa56a, 0xb54b, 0x8528, 0x9509, 0xe5ee, 0xf5cf, 0xc5ac, 0xd58d,
1092                 0x3653, 0x2672, 0x1611, 0x0630, 0x76d7, 0x66f6, 0x5695, 0x46b4,
1093                 0xb75b, 0xa77a, 0x9719, 0x8738, 0xf7df, 0xe7fe, 0xd79d, 0xc7bc,
1094                 0x48c4, 0x58e5, 0x6886, 0x78a7, 0x0840, 0x1861, 0x2802, 0x3823,
1095                 0xc9cc, 0xd9ed, 0xe98e, 0xf9af, 0x8948, 0x9969, 0xa90a, 0xb92b,
1096                 0x5af5, 0x4ad4, 0x7ab7, 0x6a96, 0x1a71, 0x0a50, 0x3a33, 0x2a12,
1097                 0xdbfd, 0xcbdc, 0xfbbf, 0xeb9e, 0x9b79, 0x8b58, 0xbb3b, 0xab1a,
1098                 0x6ca6, 0x7c87, 0x4ce4, 0x5cc5, 0x2c22, 0x3c03, 0x0c60, 0x1c41,
1099                 0xedae, 0xfd8f, 0xcdec, 0xddcd, 0xad2a, 0xbd0b, 0x8d68, 0x9d49,
1100                 0x7e97, 0x6eb6, 0x5ed5, 0x4ef4, 0x3e13, 0x2e32, 0x1e51, 0x0e70,
1101                 0xff9f, 0xefbe, 0xdfdd, 0xcffc, 0xbf1b, 0xaf3a, 0x9f59, 0x8f78,
1102                 0x9188, 0x81a9, 0xb1ca, 0xa1eb, 0xd10c, 0xc12d, 0xf14e, 0xe16f,
1103                 0x1080, 0x00a1, 0x30c2, 0x20e3, 0x5004, 0x4025, 0x7046, 0x6067,
1104                 0x83b9, 0x9398, 0xa3fb, 0xb3da, 0xc33d, 0xd31c, 0xe37f, 0xf35e,
1105                 0x02b1, 0x1290, 0x22f3, 0x32d2, 0x4235, 0x5214, 0x6277, 0x7256,
1106                 0xb5ea, 0xa5cb, 0x95a8, 0x8589, 0xf56e, 0xe54f, 0xd52c, 0xc50d,
1107                 0x34e2, 0x24c3, 0x14a0, 0x0481, 0x7466, 0x6447, 0x5424, 0x4405,
1108                 0xa7db, 0xb7fa, 0x8799, 0x97b8, 0xe75f, 0xf77e, 0xc71d, 0xd73c,
1109                 0x26d3, 0x36f2, 0x0691, 0x16b0, 0x6657, 0x7676, 0x4615, 0x5634,
1110                 0xd94c, 0xc96d, 0xf90e, 0xe92f, 0x99c8, 0x89e9, 0xb98a, 0xa9ab,
1111                 0x5844, 0x4865, 0x7806, 0x6827, 0x18c0, 0x08e1, 0x3882, 0x28a3,
1112                 0xcb7d, 0xdb5c, 0xeb3f, 0xfb1e, 0x8bf9, 0x9bd8, 0xabbb, 0xbb9a,
1113                 0x4a75, 0x5a54, 0x6a37, 0x7a16, 0x0af1, 0x1ad0, 0x2ab3, 0x3a92,
1114                 0xfd2e, 0xed0f, 0xdd6c, 0xcd4d, 0xbdaa, 0xad8b, 0x9de8, 0x8dc9,
1115                 0x7c26, 0x6c07, 0x5c64, 0x4c45, 0x3ca2, 0x2c83, 0x1ce0, 0x0cc1,
1116                 0xef1f, 0xff3e, 0xcf5d, 0xdf7c, 0xaf9b, 0xbfba, 0x8fd9, 0x9ff8,
1117                 0x6e17, 0x7e36, 0x4e55, 0x5e74, 0x2e93, 0x3eb2, 0x0ed1, 0x1ef0
1118         };
1119
1120         const uint8_t *src = (uint8_t*)data;
1121
1122         /* fetch the current value into a local and rip through the source data */
1123         while (length-- != 0)
1124                 crc = (crc << 8) ^ s_table[(crc >> 8) ^ *src++];
1125         return crc;
1126 }
1127
1128 /*-------------------------------------------------
1129         compressed - test if CHD file is compressed
1130 +-------------------------------------------------*/
1131
1132 static inline int chd_compressed(chd_header* header) {
1133         return header->compression[0] != CHD_CODEC_NONE;
1134 }
1135
1136 /*-------------------------------------------------
1137         decompress_v5_map - decompress the v5 map
1138 -------------------------------------------------*/
1139
1140 static chd_error decompress_v5_map(chd_file* chd, chd_header* header)
1141 {
1142         int result = 0;
1143         int hunknum;
1144         int repcount = 0;
1145         uint8_t lastcomp = 0;
1146         uint32_t last_self = 0;
1147         uint64_t last_parent = 0;
1148         struct bitstream* bitbuf;
1149         uint32_t mapbytes;
1150         uint64_t firstoffs;
1151         uint16_t mapcrc;
1152         uint8_t lengthbits;
1153         uint8_t selfbits;
1154         uint8_t parentbits;
1155         uint8_t *compressed_ptr;
1156         uint8_t rawbuf[16];
1157         struct huffman_decoder* decoder;
1158         enum huffman_error err;
1159         uint64_t curoffset;
1160         int rawmapsize = map_size_v5(header);
1161
1162         if (!chd_compressed(header))
1163         {
1164                 header->rawmap = (uint8_t*)malloc(rawmapsize);
1165                 int result;
1166                 core_fseek(chd->file, header->mapoffset, SEEK_SET);
1167                 result = core_fread(chd->file, header->rawmap, rawmapsize);
1168                 return CHDERR_NONE;
1169         }
1170
1171         /* read the reader */
1172         core_fseek(chd->file, header->mapoffset, SEEK_SET);
1173         result = core_fread(chd->file, rawbuf, sizeof(rawbuf));
1174         mapbytes = get_bigendian_uint32(&rawbuf[0]);
1175         firstoffs = get_bigendian_uint48(&rawbuf[4]);
1176         mapcrc = get_bigendian_uint16(&rawbuf[10]);
1177         lengthbits = rawbuf[12];
1178         selfbits = rawbuf[13];
1179         parentbits = rawbuf[14];
1180
1181         /* now read the map */
1182         compressed_ptr = (uint8_t*)malloc(sizeof(uint8_t) * mapbytes);
1183         core_fseek(chd->file, header->mapoffset + 16, SEEK_SET);
1184         result = core_fread(chd->file, compressed_ptr, mapbytes);
1185         bitbuf = create_bitstream(compressed_ptr, sizeof(uint8_t) * mapbytes);
1186         header->rawmap = (uint8_t*)malloc(rawmapsize);
1187
1188         /* first decode the compression types */
1189         decoder = create_huffman_decoder(16, 8);
1190         err = huffman_import_tree_rle(decoder, bitbuf);
1191         if (err != HUFFERR_NONE)
1192                 return CHDERR_DECOMPRESSION_ERROR;
1193         for (hunknum = 0; hunknum < header->hunkcount; hunknum++)
1194         {
1195                 uint8_t *rawmap = header->rawmap + (hunknum * 12);
1196                 if (repcount > 0)
1197                         rawmap[0] = lastcomp, repcount--;
1198                 else
1199                 {
1200                         uint8_t val = huffman_decode_one(decoder, bitbuf);
1201                         if (val == COMPRESSION_RLE_SMALL)
1202                                 rawmap[0] = lastcomp, repcount = 2 + huffman_decode_one(decoder, bitbuf);
1203                         else if (val == COMPRESSION_RLE_LARGE)
1204                                 rawmap[0] = lastcomp, repcount = 2 + 16 + (huffman_decode_one(decoder, bitbuf) << 4), repcount += huffman_decode_one(decoder, bitbuf);
1205                         else
1206                                 rawmap[0] = lastcomp = val;
1207                 }
1208         }
1209
1210         /* then iterate through the hunks and extract the needed data */
1211         curoffset = firstoffs;
1212         for (hunknum = 0; hunknum < header->hunkcount; hunknum++)
1213         {
1214                 uint8_t *rawmap = header->rawmap + (hunknum * 12);
1215                 uint64_t offset = curoffset;
1216                 uint32_t length = 0;
1217                 uint16_t crc = 0;
1218                 switch (rawmap[0])
1219                 {
1220                         /* base types */
1221                         case COMPRESSION_TYPE_0:
1222                         case COMPRESSION_TYPE_1:
1223                         case COMPRESSION_TYPE_2:
1224                         case COMPRESSION_TYPE_3:
1225                                 curoffset += length = bitstream_read(bitbuf, lengthbits);
1226                                 crc = bitstream_read(bitbuf, 16);
1227                                 break;
1228
1229                         case COMPRESSION_NONE:
1230                                 curoffset += length = header->hunkbytes;
1231                                 crc = bitstream_read(bitbuf, 16);
1232                                 break;
1233
1234                         case COMPRESSION_SELF:
1235                                 last_self = offset = bitstream_read(bitbuf, selfbits);
1236                                 break;
1237
1238                         case COMPRESSION_PARENT:
1239                                 offset = bitstream_read(bitbuf, parentbits);
1240                                 last_parent = offset;
1241                                 break;
1242
1243                         /* pseudo-types; convert into base types */
1244                         case COMPRESSION_SELF_1:
1245                                 last_self++;
1246                         case COMPRESSION_SELF_0:
1247                                 rawmap[0] = COMPRESSION_SELF;
1248                                 offset = last_self;
1249                                 break;
1250
1251                         case COMPRESSION_PARENT_SELF:
1252                                 rawmap[0] = COMPRESSION_PARENT;
1253                                 last_parent = offset = ( ((uint64_t)hunknum) * ((uint64_t)header->hunkbytes) ) / header->unitbytes;
1254                                 break;
1255
1256                         case COMPRESSION_PARENT_1:
1257                                 last_parent += header->hunkbytes / header->unitbytes;
1258                         case COMPRESSION_PARENT_0:
1259                                 rawmap[0] = COMPRESSION_PARENT;
1260                                 offset = last_parent;
1261                                 break;
1262                 }
1263                 /* UINT24 length */
1264                 put_bigendian_uint24(&rawmap[1], length);
1265
1266                 /* UINT48 offset */
1267                 put_bigendian_uint48(&rawmap[4], offset);
1268
1269                 /* crc16 */
1270                 put_bigendian_uint16(&rawmap[10], crc);
1271         }
1272
1273         free(compressed_ptr);
1274         free(bitbuf);
1275         free(decoder->lookup);
1276         free(decoder->huffnode);
1277         free(decoder);
1278
1279         /* verify the final CRC */
1280         if (crc16(&header->rawmap[0], header->hunkcount * 12) != mapcrc)
1281                 return CHDERR_DECOMPRESSION_ERROR;
1282
1283         return CHDERR_NONE;
1284 }
1285
1286 /*-------------------------------------------------
1287     map_extract_old - extract a single map
1288     entry in old format from the datastream
1289 -------------------------------------------------*/
1290
1291 static inline void map_extract_old(const UINT8 *base, map_entry *entry, UINT32 hunkbytes)
1292 {
1293         entry->offset = get_bigendian_uint64(&base[0]);
1294         entry->crc = 0;
1295         entry->length = entry->offset >> 44;
1296         entry->flags = MAP_ENTRY_FLAG_NO_CRC | ((entry->length == hunkbytes) ? V34_MAP_ENTRY_TYPE_UNCOMPRESSED : V34_MAP_ENTRY_TYPE_COMPRESSED);
1297 #ifdef __MWERKS__
1298         entry->offset = entry->offset & 0x00000FFFFFFFFFFFLL;
1299 #else
1300         entry->offset = (entry->offset << 20) >> 20;
1301 #endif
1302 }
1303
1304 /***************************************************************************
1305     CHD FILE MANAGEMENT
1306 ***************************************************************************/
1307
1308 /*-------------------------------------------------
1309     chd_open_file - open a CHD file for access
1310 -------------------------------------------------*/
1311
1312 chd_error chd_open_file(core_file *file, int mode, chd_file *parent, chd_file **chd)
1313 {
1314         chd_file *newchd = NULL;
1315         chd_error err;
1316         int intfnum;
1317
1318         /* verify parameters */
1319         if (file == NULL)
1320                 EARLY_EXIT(err = CHDERR_INVALID_PARAMETER);
1321
1322         /* punt if invalid parent */
1323         if (parent != NULL && parent->cookie != COOKIE_VALUE)
1324                 EARLY_EXIT(err = CHDERR_INVALID_PARAMETER);
1325
1326         /* allocate memory for the final result */
1327         newchd = (chd_file *)malloc(sizeof(**chd));
1328         if (newchd == NULL)
1329                 EARLY_EXIT(err = CHDERR_OUT_OF_MEMORY);
1330         memset(newchd, 0, sizeof(*newchd));
1331         newchd->cookie = COOKIE_VALUE;
1332         newchd->parent = parent;
1333         newchd->file = file;
1334
1335         /* now attempt to read the header */
1336         err = header_read(newchd, &newchd->header);
1337         if (err != CHDERR_NONE)
1338                 EARLY_EXIT(err);
1339
1340         /* validate the header */
1341         err = header_validate(&newchd->header);
1342         if (err != CHDERR_NONE)
1343                 EARLY_EXIT(err);
1344
1345         /* make sure we don't open a read-only file writeable */
1346         if (mode == CHD_OPEN_READWRITE && !(newchd->header.flags & CHDFLAGS_IS_WRITEABLE))
1347                 EARLY_EXIT(err = CHDERR_FILE_NOT_WRITEABLE);
1348
1349         /* also, never open an older version writeable */
1350         if (mode == CHD_OPEN_READWRITE && newchd->header.version < CHD_HEADER_VERSION)
1351                 EARLY_EXIT(err = CHDERR_UNSUPPORTED_VERSION);
1352
1353         /* if we need a parent, make sure we have one */
1354         if (parent == NULL && (newchd->header.flags & CHDFLAGS_HAS_PARENT))
1355                 EARLY_EXIT(err = CHDERR_REQUIRES_PARENT);
1356
1357         /* make sure we have a valid parent */
1358         if (parent != NULL)
1359         {
1360                 /* check MD5 if it isn't empty */
1361                 if (memcmp(nullmd5, newchd->header.parentmd5, sizeof(newchd->header.parentmd5)) != 0 &&
1362                         memcmp(nullmd5, newchd->parent->header.md5, sizeof(newchd->parent->header.md5)) != 0 &&
1363                         memcmp(newchd->parent->header.md5, newchd->header.parentmd5, sizeof(newchd->header.parentmd5)) != 0)
1364                         EARLY_EXIT(err = CHDERR_INVALID_PARENT);
1365
1366                 /* check SHA1 if it isn't empty */
1367                 if (memcmp(nullsha1, newchd->header.parentsha1, sizeof(newchd->header.parentsha1)) != 0 &&
1368                         memcmp(nullsha1, newchd->parent->header.sha1, sizeof(newchd->parent->header.sha1)) != 0 &&
1369                         memcmp(newchd->parent->header.sha1, newchd->header.parentsha1, sizeof(newchd->header.parentsha1)) != 0)
1370                         EARLY_EXIT(err = CHDERR_INVALID_PARENT);
1371         }
1372
1373         /* now read the hunk map */
1374         if (newchd->header.version < 5)
1375         {
1376                 err = map_read(newchd);
1377         }
1378         else
1379         {
1380                 err = decompress_v5_map(newchd, &(newchd->header));
1381         }
1382         if (err != CHDERR_NONE)
1383                 EARLY_EXIT(err);
1384
1385
1386         /* allocate and init the hunk cache */
1387         newchd->cache = (UINT8 *)malloc(newchd->header.hunkbytes);
1388         newchd->compare = (UINT8 *)malloc(newchd->header.hunkbytes);
1389         if (newchd->cache == NULL || newchd->compare == NULL)
1390                 EARLY_EXIT(err = CHDERR_OUT_OF_MEMORY);
1391         newchd->cachehunk = ~0;
1392         newchd->comparehunk = ~0;
1393
1394         /* allocate the temporary compressed buffer */
1395         newchd->compressed = (UINT8 *)malloc(newchd->header.hunkbytes);
1396         if (newchd->compressed == NULL)
1397                 EARLY_EXIT(err = CHDERR_OUT_OF_MEMORY);
1398
1399         /* find the codec interface */
1400         if (newchd->header.version < 5)
1401         {
1402                 for (intfnum = 0; intfnum < ARRAY_LENGTH(codec_interfaces); intfnum++)
1403                 {
1404                         if (codec_interfaces[intfnum].compression == newchd->header.compression[0])
1405                         {
1406                                 newchd->codecintf[0] = &codec_interfaces[intfnum];
1407                                 break;
1408                         }
1409                 }
1410
1411                 if (intfnum == ARRAY_LENGTH(codec_interfaces))
1412                         EARLY_EXIT(err = CHDERR_UNSUPPORTED_FORMAT);
1413
1414                 /* initialize the codec */
1415                 if (newchd->codecintf[0]->init != NULL)
1416                 {
1417                         err = (*newchd->codecintf[0]->init)(&newchd->zlib_codec_data, newchd->header.hunkbytes);
1418                         if (err != CHDERR_NONE)
1419                                 EARLY_EXIT(err);
1420                 }
1421         }
1422         else
1423         {
1424                 int decompnum;
1425                 /* verify the compression types and initialize the codecs */
1426                 for (decompnum = 0; decompnum < ARRAY_LENGTH(newchd->header.compression); decompnum++)
1427                 {
1428                         int i;
1429                         for (i = 0 ; i < ARRAY_LENGTH(codec_interfaces) ; i++)
1430                         {
1431                                 if (codec_interfaces[i].compression == newchd->header.compression[decompnum])
1432                                 {
1433                                         newchd->codecintf[decompnum] = &codec_interfaces[i];
1434                                         break;
1435                                 }
1436                         }
1437
1438                         if (newchd->codecintf[decompnum] == NULL && newchd->header.compression[decompnum] != 0)
1439                                 EARLY_EXIT(err = CHDERR_UNSUPPORTED_FORMAT);
1440
1441                         /* initialize the codec */
1442                         if (newchd->codecintf[decompnum]->init != NULL)
1443                         {
1444                                 void* codec = NULL;
1445                                 switch (newchd->header.compression[decompnum])
1446                                 {
1447                                         case CHD_CODEC_ZLIB:
1448                                                 codec = &newchd->zlib_codec_data;
1449                                                 break;
1450
1451                                         case CHD_CODEC_CD_ZLIB:
1452                                                 codec = &newchd->cdzl_codec_data;
1453                                                 break;
1454
1455                                         case CHD_CODEC_CD_LZMA:
1456                                                 codec = &newchd->cdlz_codec_data;
1457                                                 break;
1458
1459                                         case CHD_CODEC_CD_FLAC:
1460                                                 codec = &newchd->cdfl_codec_data;
1461                                                 break;
1462                                 }
1463
1464                                 if (codec == NULL)
1465                                         EARLY_EXIT(err = CHDERR_UNSUPPORTED_FORMAT);
1466
1467                                 err = (*newchd->codecintf[decompnum]->init)(codec, newchd->header.hunkbytes);
1468                                 if (err != CHDERR_NONE)
1469                                         EARLY_EXIT(err);
1470                         }
1471                 }
1472         }
1473
1474         /* all done */
1475         *chd = newchd;
1476         return CHDERR_NONE;
1477
1478 cleanup:
1479         if (newchd != NULL)
1480                 chd_close(newchd);
1481         return err;
1482 }
1483
1484 /*-------------------------------------------------
1485     chd_precache - precache underlying file in
1486     memory
1487 -------------------------------------------------*/
1488
1489 chd_error chd_precache(chd_file *chd)
1490 {
1491         ssize_t size, count;
1492
1493         if (chd->file_cache == NULL)
1494         {
1495                 core_fseek(chd->file, 0, SEEK_END);
1496                 size = core_ftell(chd->file);
1497                 if (size <= 0)
1498                         return CHDERR_INVALID_DATA;
1499                 chd->file_cache = malloc(size);
1500                 if (chd->file_cache == NULL)
1501                         return CHDERR_OUT_OF_MEMORY;
1502                 core_fseek(chd->file, 0, SEEK_SET);
1503                 count = core_fread(chd->file, chd->file_cache, size);
1504                 if (count != size)
1505                 {
1506                         free(chd->file_cache);
1507                         chd->file_cache = NULL;
1508                         return CHDERR_READ_ERROR;
1509                 }
1510         }
1511
1512         return CHDERR_NONE;
1513 }
1514
1515 /*-------------------------------------------------
1516     chd_open - open a CHD file by
1517     filename
1518 -------------------------------------------------*/
1519
1520 chd_error chd_open(const char *filename, int mode, chd_file *parent, chd_file **chd)
1521 {
1522         chd_error err;
1523         core_file *file = NULL;
1524         UINT32 openflags;
1525
1526         /* choose the proper mode */
1527         switch(mode)
1528         {
1529                 case CHD_OPEN_READ:
1530                         break;
1531
1532                 default:
1533                         err = CHDERR_INVALID_PARAMETER;
1534                         goto cleanup;
1535         }
1536
1537         /* open the file */
1538         file = core_fopen(filename);
1539         if (file == 0)
1540         {
1541                 err = CHDERR_FILE_NOT_FOUND;
1542                 goto cleanup;
1543         }
1544
1545         /* now open the CHD */
1546         err = chd_open_file(file, mode, parent, chd);
1547         if (err != CHDERR_NONE)
1548                 goto cleanup;
1549
1550         /* we now own this file */
1551         (*chd)->owns_file = TRUE;
1552
1553 cleanup:
1554         if ((err != CHDERR_NONE) && (file != NULL))
1555                 core_fclose(file);
1556         return err;
1557 }
1558
1559 /*-------------------------------------------------
1560     chd_close - close a CHD file for access
1561 -------------------------------------------------*/
1562
1563 void chd_close(chd_file *chd)
1564 {
1565         /* punt if NULL or invalid */
1566         if (chd == NULL || chd->cookie != COOKIE_VALUE)
1567                 return;
1568
1569         /* deinit the codec */
1570         if (chd->header.version < 5)
1571         {
1572                 if (chd->codecintf[0] != NULL && chd->codecintf[0]->free != NULL)
1573                         (*chd->codecintf[0]->free)(&chd->zlib_codec_data);
1574         }
1575         else
1576         {
1577         int i;
1578                 /* Free the codecs */
1579                 for (i = 0 ; i < ARRAY_LENGTH(chd->codecintf); i++)
1580                 {
1581                         void* codec = NULL;
1582
1583                         if (chd->codecintf[i] == NULL)
1584                                 continue;
1585
1586                         switch (chd->codecintf[i]->compression)
1587                         {
1588                                 case CHD_CODEC_CD_LZMA:
1589                                         codec = &chd->cdlz_codec_data;
1590                                         break;
1591
1592                                 case CHD_CODEC_ZLIB:
1593                                         codec = &chd->zlib_codec_data;
1594                                         break;
1595
1596                                 case CHD_CODEC_CD_ZLIB:
1597                                         codec = &chd->cdzl_codec_data;
1598                                         break;
1599
1600                                 case CHD_CODEC_CD_FLAC:
1601                                         codec = &chd->cdfl_codec_data;
1602                                         break;
1603                         }
1604
1605                         if (codec)
1606                         {
1607                                 (*chd->codecintf[i]->free)(codec);
1608                         }
1609                 }
1610
1611                 /* Free the raw map */
1612                 if (chd->header.rawmap != NULL)
1613                         free(chd->header.rawmap);
1614         }
1615
1616         /* free the compressed data buffer */
1617         if (chd->compressed != NULL)
1618                 free(chd->compressed);
1619
1620         /* free the hunk cache and compare data */
1621         if (chd->compare != NULL)
1622                 free(chd->compare);
1623         if (chd->cache != NULL)
1624                 free(chd->cache);
1625
1626         /* free the hunk map */
1627         if (chd->map != NULL)
1628                 free(chd->map);
1629
1630         /* free the CRC table */
1631         if (chd->crctable != NULL)
1632                 free(chd->crctable);
1633
1634         /* free the CRC map */
1635         if (chd->crcmap != NULL)
1636                 free(chd->crcmap);
1637
1638         /* close the file */
1639         if (chd->owns_file && chd->file != NULL)
1640                 core_fclose(chd->file);
1641
1642         if (PRINTF_MAX_HUNK) printf("Max hunk = %d/%d\n", chd->maxhunk, chd->header.totalhunks);
1643
1644         if (chd->file_cache)
1645                 free(chd->file_cache);
1646
1647         /* free our memory */
1648         free(chd);
1649 }
1650
1651 /*-------------------------------------------------
1652     chd_core_file - return the associated
1653     core_file
1654 -------------------------------------------------*/
1655
1656 core_file *chd_core_file(chd_file *chd)
1657 {
1658         return chd->file;
1659 }
1660
1661 /*-------------------------------------------------
1662     chd_error_string - return an error string for
1663     the given CHD error
1664 -------------------------------------------------*/
1665
1666 const char *chd_error_string(chd_error err)
1667 {
1668         switch (err)
1669         {
1670                 case CHDERR_NONE:                                               return "no error";
1671                 case CHDERR_NO_INTERFACE:                               return "no drive interface";
1672                 case CHDERR_OUT_OF_MEMORY:                              return "out of memory";
1673                 case CHDERR_INVALID_FILE:                               return "invalid file";
1674                 case CHDERR_INVALID_PARAMETER:                  return "invalid parameter";
1675                 case CHDERR_INVALID_DATA:                               return "invalid data";
1676                 case CHDERR_FILE_NOT_FOUND:                             return "file not found";
1677                 case CHDERR_REQUIRES_PARENT:                    return "requires parent";
1678                 case CHDERR_FILE_NOT_WRITEABLE:                 return "file not writeable";
1679                 case CHDERR_READ_ERROR:                                 return "read error";
1680                 case CHDERR_WRITE_ERROR:                                return "write error";
1681                 case CHDERR_CODEC_ERROR:                                return "codec error";
1682                 case CHDERR_INVALID_PARENT:                             return "invalid parent";
1683                 case CHDERR_HUNK_OUT_OF_RANGE:                  return "hunk out of range";
1684                 case CHDERR_DECOMPRESSION_ERROR:                return "decompression error";
1685                 case CHDERR_COMPRESSION_ERROR:                  return "compression error";
1686                 case CHDERR_CANT_CREATE_FILE:                   return "can't create file";
1687                 case CHDERR_CANT_VERIFY:                                return "can't verify file";
1688                 case CHDERR_NOT_SUPPORTED:                              return "operation not supported";
1689                 case CHDERR_METADATA_NOT_FOUND:                 return "can't find metadata";
1690                 case CHDERR_INVALID_METADATA_SIZE:              return "invalid metadata size";
1691                 case CHDERR_UNSUPPORTED_VERSION:                return "unsupported CHD version";
1692                 case CHDERR_VERIFY_INCOMPLETE:                  return "incomplete verify";
1693                 case CHDERR_INVALID_METADATA:                   return "invalid metadata";
1694                 case CHDERR_INVALID_STATE:                              return "invalid state";
1695                 case CHDERR_OPERATION_PENDING:                  return "operation pending";
1696                 case CHDERR_NO_ASYNC_OPERATION:                 return "no async operation in progress";
1697                 case CHDERR_UNSUPPORTED_FORMAT:                 return "unsupported format";
1698                 default:                                                                return "undocumented error";
1699         }
1700 }
1701
1702 /***************************************************************************
1703     CHD HEADER MANAGEMENT
1704 ***************************************************************************/
1705
1706 /*-------------------------------------------------
1707     chd_get_header - return a pointer to the
1708     extracted header data
1709 -------------------------------------------------*/
1710
1711 const chd_header *chd_get_header(chd_file *chd)
1712 {
1713         /* punt if NULL or invalid */
1714         if (chd == NULL || chd->cookie != COOKIE_VALUE)
1715                 return NULL;
1716
1717         return &chd->header;
1718 }
1719
1720 /***************************************************************************
1721     CORE DATA READ/WRITE
1722 ***************************************************************************/
1723
1724 /*-------------------------------------------------
1725     chd_read - read a single hunk from the CHD
1726     file
1727 -------------------------------------------------*/
1728
1729 chd_error chd_read(chd_file *chd, UINT32 hunknum, void *buffer)
1730 {
1731         /* punt if NULL or invalid */
1732         if (chd == NULL || chd->cookie != COOKIE_VALUE)
1733                 return CHDERR_INVALID_PARAMETER;
1734
1735         /* if we're past the end, fail */
1736         if (hunknum >= chd->header.totalhunks)
1737                 return CHDERR_HUNK_OUT_OF_RANGE;
1738
1739         /* perform the read */
1740         return hunk_read_into_memory(chd, hunknum, (UINT8 *)buffer);
1741 }
1742
1743 /***************************************************************************
1744     METADATA MANAGEMENT
1745 ***************************************************************************/
1746
1747 /*-------------------------------------------------
1748     chd_get_metadata - get the indexed metadata
1749     of the given type
1750 -------------------------------------------------*/
1751
1752 chd_error chd_get_metadata(chd_file *chd, UINT32 searchtag, UINT32 searchindex, void *output, UINT32 outputlen, UINT32 *resultlen, UINT32 *resulttag, UINT8 *resultflags)
1753 {
1754         metadata_entry metaentry;
1755         chd_error err;
1756         UINT32 count;
1757
1758         /* if we didn't find it, just return */
1759         err = metadata_find_entry(chd, searchtag, searchindex, &metaentry);
1760         if (err != CHDERR_NONE)
1761         {
1762                 /* unless we're an old version and they are requesting hard disk metadata */
1763                 if (chd->header.version < 3 && (searchtag == HARD_DISK_METADATA_TAG || searchtag == CHDMETATAG_WILDCARD) && searchindex == 0)
1764                 {
1765                         char faux_metadata[256];
1766                         UINT32 faux_length;
1767
1768                         /* fill in the faux metadata */
1769                         sprintf(faux_metadata, HARD_DISK_METADATA_FORMAT, chd->header.obsolete_cylinders, chd->header.obsolete_heads, chd->header.obsolete_sectors, chd->header.hunkbytes / chd->header.obsolete_hunksize);
1770                         faux_length = (UINT32)strlen(faux_metadata) + 1;
1771
1772                         /* copy the metadata itself */
1773                         memcpy(output, faux_metadata, MIN(outputlen, faux_length));
1774
1775                         /* return the length of the data and the tag */
1776                         if (resultlen != NULL)
1777                                 *resultlen = faux_length;
1778                         if (resulttag != NULL)
1779                                 *resulttag = HARD_DISK_METADATA_TAG;
1780                         return CHDERR_NONE;
1781                 }
1782                 return err;
1783         }
1784
1785         /* read the metadata */
1786         outputlen = MIN(outputlen, metaentry.length);
1787         core_fseek(chd->file, metaentry.offset + METADATA_HEADER_SIZE, SEEK_SET);
1788         count = core_fread(chd->file, output, outputlen);
1789         if (count != outputlen)
1790                 return CHDERR_READ_ERROR;
1791
1792         /* return the length of the data and the tag */
1793         if (resultlen != NULL)
1794                 *resultlen = metaentry.length;
1795         if (resulttag != NULL)
1796                 *resulttag = metaentry.metatag;
1797         if (resultflags != NULL)
1798                 *resultflags = metaentry.flags;
1799         return CHDERR_NONE;
1800 }
1801
1802 /***************************************************************************
1803     CODEC INTERFACES
1804 ***************************************************************************/
1805
1806 /*-------------------------------------------------
1807     chd_codec_config - set internal codec
1808     parameters
1809 -------------------------------------------------*/
1810
1811 chd_error chd_codec_config(chd_file *chd, int param, void *config)
1812 {
1813         return CHDERR_INVALID_PARAMETER;
1814 }
1815
1816 /*-------------------------------------------------
1817     chd_get_codec_name - get the name of a
1818     particular codec
1819 -------------------------------------------------*/
1820
1821 const char *chd_get_codec_name(UINT32 codec)
1822 {
1823         return "Unknown";
1824 }
1825
1826 /***************************************************************************
1827     INTERNAL HEADER OPERATIONS
1828 ***************************************************************************/
1829
1830 /*-------------------------------------------------
1831     header_validate - check the validity of a
1832     CHD header
1833 -------------------------------------------------*/
1834
1835 static chd_error header_validate(const chd_header *header)
1836 {
1837         int intfnum;
1838
1839         /* require a valid version */
1840         if (header->version == 0 || header->version > CHD_HEADER_VERSION)
1841                 return CHDERR_UNSUPPORTED_VERSION;
1842
1843         /* require a valid length */
1844         if ((header->version == 1 && header->length != CHD_V1_HEADER_SIZE) ||
1845                 (header->version == 2 && header->length != CHD_V2_HEADER_SIZE) ||
1846                 (header->version == 3 && header->length != CHD_V3_HEADER_SIZE) ||
1847                 (header->version == 4 && header->length != CHD_V4_HEADER_SIZE) ||
1848                 (header->version == 5 && header->length != CHD_V5_HEADER_SIZE))
1849                 return CHDERR_INVALID_PARAMETER;
1850
1851         /* Do not validate v5 header */
1852         if (header->version <= 4)
1853         {
1854                 /* require valid flags */
1855                 if (header->flags & CHDFLAGS_UNDEFINED)
1856                         return CHDERR_INVALID_PARAMETER;
1857
1858                 /* require a supported compression mechanism */
1859                 for (intfnum = 0; intfnum < ARRAY_LENGTH(codec_interfaces); intfnum++)
1860                         if (codec_interfaces[intfnum].compression == header->compression[0])
1861                                 break;
1862
1863                 if (intfnum == ARRAY_LENGTH(codec_interfaces))
1864                         return CHDERR_INVALID_PARAMETER;
1865
1866                 /* require a valid hunksize */
1867                 if (header->hunkbytes == 0 || header->hunkbytes >= 65536 * 256)
1868                         return CHDERR_INVALID_PARAMETER;
1869
1870                 /* require a valid hunk count */
1871                 if (header->totalhunks == 0)
1872                         return CHDERR_INVALID_PARAMETER;
1873
1874                 /* require a valid MD5 and/or SHA1 if we're using a parent */
1875                 if ((header->flags & CHDFLAGS_HAS_PARENT) && memcmp(header->parentmd5, nullmd5, sizeof(nullmd5)) == 0 && memcmp(header->parentsha1, nullsha1, sizeof(nullsha1)) == 0)
1876                         return CHDERR_INVALID_PARAMETER;
1877
1878                 /* if we're V3 or later, the obsolete fields must be 0 */
1879                 if (header->version >= 3 &&
1880                         (header->obsolete_cylinders != 0 || header->obsolete_sectors != 0 ||
1881                          header->obsolete_heads != 0 || header->obsolete_hunksize != 0))
1882                         return CHDERR_INVALID_PARAMETER;
1883
1884                 /* if we're pre-V3, the obsolete fields must NOT be 0 */
1885                 if (header->version < 3 &&
1886                         (header->obsolete_cylinders == 0 || header->obsolete_sectors == 0 ||
1887                          header->obsolete_heads == 0 || header->obsolete_hunksize == 0))
1888                         return CHDERR_INVALID_PARAMETER;
1889         }
1890
1891         return CHDERR_NONE;
1892 }
1893
1894 /*-------------------------------------------------
1895     header_guess_unitbytes - for older CHD formats,
1896     guess at the bytes/unit based on metadata
1897 -------------------------------------------------*/
1898
1899 static UINT32 header_guess_unitbytes(chd_file *chd)
1900 {
1901         /* look for hard disk metadata; if found, then the unit size == sector size */
1902         char metadata[512];
1903         int i0, i1, i2, i3;
1904         if (chd_get_metadata(chd, HARD_DISK_METADATA_TAG, 0, metadata, sizeof(metadata), NULL, NULL, NULL) == CHDERR_NONE &&
1905                 sscanf(metadata, HARD_DISK_METADATA_FORMAT, &i0, &i1, &i2, &i3) == 4)
1906                 return i3;
1907
1908         /* look for CD-ROM metadata; if found, then the unit size == CD frame size */
1909         if (chd_get_metadata(chd, CDROM_OLD_METADATA_TAG, 0, metadata, sizeof(metadata), NULL, NULL, NULL) == CHDERR_NONE ||
1910                 chd_get_metadata(chd, CDROM_TRACK_METADATA_TAG, 0, metadata, sizeof(metadata), NULL, NULL, NULL) == CHDERR_NONE ||
1911                 chd_get_metadata(chd, CDROM_TRACK_METADATA2_TAG, 0, metadata, sizeof(metadata), NULL, NULL, NULL) == CHDERR_NONE ||
1912                 chd_get_metadata(chd, GDROM_OLD_METADATA_TAG, 0, metadata, sizeof(metadata), NULL, NULL, NULL) == CHDERR_NONE ||
1913                 chd_get_metadata(chd, GDROM_TRACK_METADATA_TAG, 0, metadata, sizeof(metadata), NULL, NULL, NULL) == CHDERR_NONE)
1914                 return CD_FRAME_SIZE;
1915
1916         /* otherwise, just map 1:1 with the hunk size */
1917         return chd->header.hunkbytes;
1918 }
1919
1920 /*-------------------------------------------------
1921     header_read - read a CHD header into the
1922     internal data structure
1923 -------------------------------------------------*/
1924
1925 static chd_error header_read(chd_file *chd, chd_header *header)
1926 {
1927         UINT8 rawheader[CHD_MAX_HEADER_SIZE];
1928         UINT32 count;
1929
1930         /* punt if NULL */
1931         if (header == NULL)
1932                 return CHDERR_INVALID_PARAMETER;
1933
1934         /* punt if invalid file */
1935         if (chd->file == NULL)
1936                 return CHDERR_INVALID_FILE;
1937
1938         /* seek and read */
1939         core_fseek(chd->file, 0, SEEK_SET);
1940         count = core_fread(chd->file, rawheader, sizeof(rawheader));
1941         if (count != sizeof(rawheader))
1942                 return CHDERR_READ_ERROR;
1943
1944         /* verify the tag */
1945         if (strncmp((char *)rawheader, "MComprHD", 8) != 0)
1946                 return CHDERR_INVALID_DATA;
1947
1948         /* extract the direct data */
1949         memset(header, 0, sizeof(*header));
1950         header->length        = get_bigendian_uint32(&rawheader[8]);
1951         header->version       = get_bigendian_uint32(&rawheader[12]);
1952
1953         /* make sure it's a version we understand */
1954         if (header->version == 0 || header->version > CHD_HEADER_VERSION)
1955                 return CHDERR_UNSUPPORTED_VERSION;
1956
1957         /* make sure the length is expected */
1958         if ((header->version == 1 && header->length != CHD_V1_HEADER_SIZE) ||
1959                 (header->version == 2 && header->length != CHD_V2_HEADER_SIZE) ||
1960                 (header->version == 3 && header->length != CHD_V3_HEADER_SIZE) ||
1961                 (header->version == 4 && header->length != CHD_V4_HEADER_SIZE) ||
1962                 (header->version == 5 && header->length != CHD_V5_HEADER_SIZE))
1963
1964                 return CHDERR_INVALID_DATA;
1965
1966         /* extract the common data */
1967         header->flags           = get_bigendian_uint32(&rawheader[16]);
1968         header->compression[0]  = get_bigendian_uint32(&rawheader[20]);
1969         header->compression[1]  = CHD_CODEC_NONE;
1970         header->compression[2]  = CHD_CODEC_NONE;
1971         header->compression[3]  = CHD_CODEC_NONE;
1972
1973         /* extract the V1/V2-specific data */
1974         if (header->version < 3)
1975         {
1976                 int seclen = (header->version == 1) ? CHD_V1_SECTOR_SIZE : get_bigendian_uint32(&rawheader[76]);
1977                 header->obsolete_hunksize  = get_bigendian_uint32(&rawheader[24]);
1978                 header->totalhunks         = get_bigendian_uint32(&rawheader[28]);
1979                 header->obsolete_cylinders = get_bigendian_uint32(&rawheader[32]);
1980                 header->obsolete_heads     = get_bigendian_uint32(&rawheader[36]);
1981                 header->obsolete_sectors   = get_bigendian_uint32(&rawheader[40]);
1982                 memcpy(header->md5, &rawheader[44], CHD_MD5_BYTES);
1983                 memcpy(header->parentmd5, &rawheader[60], CHD_MD5_BYTES);
1984                 header->logicalbytes = (UINT64)header->obsolete_cylinders * (UINT64)header->obsolete_heads * (UINT64)header->obsolete_sectors * (UINT64)seclen;
1985                 header->hunkbytes = seclen * header->obsolete_hunksize;
1986                 header->unitbytes          = header_guess_unitbytes(chd);
1987                 header->unitcount          = (header->logicalbytes + header->unitbytes - 1) / header->unitbytes;
1988                 header->metaoffset = 0;
1989         }
1990
1991         /* extract the V3-specific data */
1992         else if (header->version == 3)
1993         {
1994                 header->totalhunks   = get_bigendian_uint32(&rawheader[24]);
1995                 header->logicalbytes = get_bigendian_uint64(&rawheader[28]);
1996                 header->metaoffset   = get_bigendian_uint64(&rawheader[36]);
1997                 memcpy(header->md5, &rawheader[44], CHD_MD5_BYTES);
1998                 memcpy(header->parentmd5, &rawheader[60], CHD_MD5_BYTES);
1999                 header->hunkbytes    = get_bigendian_uint32(&rawheader[76]);
2000                 header->unitbytes    = header_guess_unitbytes(chd);
2001                 header->unitcount    = (header->logicalbytes + header->unitbytes - 1) / header->unitbytes;
2002                 memcpy(header->sha1, &rawheader[80], CHD_SHA1_BYTES);
2003                 memcpy(header->parentsha1, &rawheader[100], CHD_SHA1_BYTES);
2004         }
2005
2006         /* extract the V4-specific data */
2007         else if (header->version == 4)
2008         {
2009                 header->totalhunks   = get_bigendian_uint32(&rawheader[24]);
2010                 header->logicalbytes = get_bigendian_uint64(&rawheader[28]);
2011                 header->metaoffset   = get_bigendian_uint64(&rawheader[36]);
2012                 header->hunkbytes    = get_bigendian_uint32(&rawheader[44]);
2013                 header->unitbytes    = header_guess_unitbytes(chd);
2014                 header->unitcount    = (header->logicalbytes + header->unitbytes - 1) / header->unitbytes;
2015                 memcpy(header->sha1, &rawheader[48], CHD_SHA1_BYTES);
2016                 memcpy(header->parentsha1, &rawheader[68], CHD_SHA1_BYTES);
2017                 memcpy(header->rawsha1, &rawheader[88], CHD_SHA1_BYTES);
2018         }
2019
2020         /* extract the V5-specific data */
2021         else if (header->version == 5)
2022         {
2023                 /* TODO */
2024                 header->compression[0]  = get_bigendian_uint32(&rawheader[16]);
2025                 header->compression[1]  = get_bigendian_uint32(&rawheader[20]);
2026                 header->compression[2]  = get_bigendian_uint32(&rawheader[24]);
2027                 header->compression[3]  = get_bigendian_uint32(&rawheader[28]);
2028                 header->logicalbytes    = get_bigendian_uint64(&rawheader[32]);
2029                 header->mapoffset       = get_bigendian_uint64(&rawheader[40]);
2030                 header->metaoffset      = get_bigendian_uint64(&rawheader[48]);
2031                 header->hunkbytes       = get_bigendian_uint32(&rawheader[56]);
2032                 header->hunkcount       = (header->logicalbytes + header->hunkbytes - 1) / header->hunkbytes;
2033                 header->unitbytes       = get_bigendian_uint32(&rawheader[60]);
2034                 header->unitcount       = (header->logicalbytes + header->unitbytes - 1) / header->unitbytes;
2035                 memcpy(header->sha1, &rawheader[84], CHD_SHA1_BYTES);
2036                 memcpy(header->parentsha1, &rawheader[104], CHD_SHA1_BYTES);
2037                 memcpy(header->rawsha1, &rawheader[64], CHD_SHA1_BYTES);
2038
2039                 /* determine properties of map entries */
2040                 header->mapentrybytes = chd_compressed(header) ? 12 : 4;
2041
2042                 /* hack */
2043                 header->totalhunks              = header->hunkcount;
2044         }
2045
2046         /* Unknown version */
2047         else
2048         {
2049                 /* TODO */
2050         }
2051
2052         /* guess it worked */
2053         return CHDERR_NONE;
2054 }
2055
2056 /***************************************************************************
2057     INTERNAL HUNK READ/WRITE
2058 ***************************************************************************/
2059
2060 /*-------------------------------------------------
2061     hunk_read_compressed - read a compressed
2062     hunk
2063 -------------------------------------------------*/
2064
2065 static UINT8* hunk_read_compressed(chd_file *chd, UINT64 offset, size_t size)
2066 {
2067         ssize_t bytes;
2068         if (chd->file_cache != NULL)
2069         {
2070                 return chd->file_cache + offset;
2071         }
2072         else
2073         {
2074                 core_fseek(chd->file, offset, SEEK_SET);
2075                 bytes = core_fread(chd->file, chd->compressed, size);
2076                 if (bytes != size)
2077                         return NULL;
2078                 return chd->compressed;
2079         }
2080 }
2081
2082 /*-------------------------------------------------
2083     hunk_read_uncompressed - read an uncompressed
2084     hunk
2085 -------------------------------------------------*/
2086
2087 static chd_error hunk_read_uncompressed(chd_file *chd, UINT64 offset, size_t size, UINT8 *dest)
2088 {
2089         ssize_t bytes;
2090         if (chd->file_cache != NULL)
2091         {
2092                 memcpy(dest, chd->file_cache + offset, size);
2093         }
2094         else
2095         {
2096                 core_fseek(chd->file, offset, SEEK_SET);
2097                 bytes = core_fread(chd->file, dest, size);
2098                 if (bytes != size)
2099                         return CHDERR_READ_ERROR;
2100         }
2101         return CHDERR_NONE;
2102 }
2103
2104 /*-------------------------------------------------
2105     hunk_read_into_cache - read a hunk into
2106     the CHD's hunk cache
2107 -------------------------------------------------*/
2108
2109 static chd_error hunk_read_into_cache(chd_file *chd, UINT32 hunknum)
2110 {
2111         chd_error err;
2112
2113         /* track the max */
2114         if (hunknum > chd->maxhunk)
2115                 chd->maxhunk = hunknum;
2116
2117         /* if we're already in the cache, we're done */
2118         if (chd->cachehunk == hunknum)
2119                 return CHDERR_NONE;
2120         chd->cachehunk = ~0;
2121
2122         /* otherwise, read the data */
2123         err = hunk_read_into_memory(chd, hunknum, chd->cache);
2124         if (err != CHDERR_NONE)
2125                 return err;
2126
2127         /* mark the hunk successfully cached in */
2128         chd->cachehunk = hunknum;
2129         return CHDERR_NONE;
2130 }
2131
2132 /*-------------------------------------------------
2133     hunk_read_into_memory - read a hunk into
2134     memory at the given location
2135 -------------------------------------------------*/
2136
2137 static chd_error hunk_read_into_memory(chd_file *chd, UINT32 hunknum, UINT8 *dest)
2138 {
2139         chd_error err;
2140
2141         /* punt if no file */
2142         if (chd->file == NULL)
2143                 return CHDERR_INVALID_FILE;
2144
2145         /* return an error if out of range */
2146         if (hunknum >= chd->header.totalhunks)
2147                 return CHDERR_HUNK_OUT_OF_RANGE;
2148
2149         if (chd->header.version < 5)
2150         {
2151                 map_entry *entry = &chd->map[hunknum];
2152                 UINT32 bytes;
2153                 UINT8* compressed_bytes;
2154
2155                 /* switch off the entry type */
2156                 switch (entry->flags & MAP_ENTRY_FLAG_TYPE_MASK)
2157                 {
2158                         /* compressed data */
2159                         case V34_MAP_ENTRY_TYPE_COMPRESSED:
2160             {
2161                 void *codec = NULL;
2162
2163                                 /* read it into the decompression buffer */
2164                                 compressed_bytes = hunk_read_compressed(chd, entry->offset, entry->length);
2165                                 if (compressed_bytes == NULL)
2166                                         return CHDERR_READ_ERROR;
2167
2168                                 /* now decompress using the codec */
2169                                 err = CHDERR_NONE;
2170                                 codec = &chd->zlib_codec_data;
2171                                 if (chd->codecintf[0]->decompress != NULL)
2172                                         err = (*chd->codecintf[0]->decompress)(codec, compressed_bytes, entry->length, dest, chd->header.hunkbytes);
2173                                 if (err != CHDERR_NONE)
2174                                         return err;
2175                                 break;
2176                         }
2177
2178                         /* uncompressed data */
2179                         case V34_MAP_ENTRY_TYPE_UNCOMPRESSED:
2180                                 err = hunk_read_uncompressed(chd, entry->offset, chd->header.hunkbytes, dest);
2181                                 if (err != CHDERR_NONE)
2182                                         return err;
2183                                 break;
2184
2185                         /* mini-compressed data */
2186                         case V34_MAP_ENTRY_TYPE_MINI:
2187                                 put_bigendian_uint64(&dest[0], entry->offset);
2188                                 for (bytes = 8; bytes < chd->header.hunkbytes; bytes++)
2189                                         dest[bytes] = dest[bytes - 8];
2190                                 break;
2191
2192                         /* self-referenced data */
2193                         case V34_MAP_ENTRY_TYPE_SELF_HUNK:
2194                                 if (chd->cachehunk == entry->offset && dest == chd->cache)
2195                                         break;
2196                                 return hunk_read_into_memory(chd, entry->offset, dest);
2197
2198                         /* parent-referenced data */
2199                         case V34_MAP_ENTRY_TYPE_PARENT_HUNK:
2200                                 err = hunk_read_into_memory(chd->parent, entry->offset, dest);
2201                                 if (err != CHDERR_NONE)
2202                                         return err;
2203                                 break;
2204                 }
2205                 return CHDERR_NONE;
2206         }
2207         else
2208         {
2209                 /* get a pointer to the map entry */
2210                 uint64_t blockoffs;
2211                 uint32_t blocklen;
2212                 uint16_t blockcrc;
2213                 void* codec = NULL;
2214                 uint8_t *rawmap = &chd->header.rawmap[chd->header.mapentrybytes * hunknum];
2215                 UINT8* compressed_bytes;
2216
2217                 /* uncompressed case */
2218                 if (!chd_compressed(&chd->header))
2219                 {
2220                         blockoffs = (uint64_t)get_bigendian_uint32(rawmap) * (uint64_t)chd->header.hunkbytes;
2221                         if (blockoffs != 0) {
2222                                 int result;
2223                                 core_fseek(chd->file, blockoffs, SEEK_SET);
2224                                 result = core_fread(chd->file, dest, chd->header.hunkbytes);
2225                         /* TODO
2226                         else if (m_parent_missing)
2227                                 throw CHDERR_REQUIRES_PARENT; */
2228                         } else if (chd->parent) {
2229                                 err = hunk_read_into_memory(chd->parent, hunknum, dest);
2230                                 if (err != CHDERR_NONE)
2231                                         return err;
2232                         } else {
2233                                 memset(dest, 0, chd->header.hunkbytes);
2234                         }
2235                         return CHDERR_NONE;
2236                 }
2237
2238                 /* compressed case */
2239                 blocklen = get_bigendian_uint24(&rawmap[1]);
2240                 blockoffs = get_bigendian_uint48(&rawmap[4]);
2241                 blockcrc = get_bigendian_uint16(&rawmap[10]);
2242                 codec = NULL;
2243                 switch (rawmap[0])
2244                 {
2245                         case COMPRESSION_TYPE_0:
2246                         case COMPRESSION_TYPE_1:
2247                         case COMPRESSION_TYPE_2:
2248                         case COMPRESSION_TYPE_3:
2249                                 compressed_bytes = hunk_read_compressed(chd, blockoffs, blocklen);
2250                                 if (compressed_bytes == NULL)
2251                                         return CHDERR_READ_ERROR;
2252                                 switch (chd->codecintf[rawmap[0]]->compression)
2253                                 {
2254                                         case CHD_CODEC_CD_LZMA:
2255                                                 codec = &chd->cdlz_codec_data;
2256                                                 break;
2257
2258                                         case CHD_CODEC_ZLIB:
2259                                                 codec = &chd->zlib_codec_data;
2260                                                 break;
2261
2262                                         case CHD_CODEC_CD_ZLIB:
2263                                                 codec = &chd->cdzl_codec_data;
2264                                                 break;
2265
2266                                         case CHD_CODEC_CD_FLAC:
2267                                                 codec = &chd->cdfl_codec_data;
2268                                                 break;
2269                                 }
2270                                 if (codec==NULL)
2271                                         return CHDERR_DECOMPRESSION_ERROR;
2272                                 chd->codecintf[rawmap[0]]->decompress(codec, compressed_bytes, blocklen, dest, chd->header.hunkbytes);
2273                                 if (dest != NULL && crc16(dest, chd->header.hunkbytes) != blockcrc)
2274                                         return CHDERR_DECOMPRESSION_ERROR;
2275                                 return CHDERR_NONE;
2276
2277                         case COMPRESSION_NONE:
2278                                 err = hunk_read_uncompressed(chd, blockoffs, blocklen, dest);
2279                                 if (err != CHDERR_NONE)
2280                                         return err;
2281                                 if (crc16(dest, chd->header.hunkbytes) != blockcrc)
2282                                         return CHDERR_DECOMPRESSION_ERROR;
2283                                 return CHDERR_NONE;
2284
2285                         case COMPRESSION_SELF:
2286                                 return hunk_read_into_memory(chd, blockoffs, dest);
2287
2288                         case COMPRESSION_PARENT:
2289 #if 0
2290                                 /* TODO */
2291                                 if (m_parent_missing)
2292                                         return CHDERR_REQUIRES_PARENT;
2293                                 return m_parent->read_bytes(uint64_t(blockoffs) * uint64_t(m_parent->unit_bytes()), dest, m_hunkbytes);
2294 #endif
2295                                 return CHDERR_DECOMPRESSION_ERROR;
2296                 }
2297                 return CHDERR_NONE;
2298         }
2299
2300         /* We should not reach this code */
2301         return CHDERR_DECOMPRESSION_ERROR;
2302 }
2303
2304 /***************************************************************************
2305     INTERNAL MAP ACCESS
2306 ***************************************************************************/
2307
2308 /*-------------------------------------------------
2309     map_read - read the initial sector map
2310 -------------------------------------------------*/
2311
2312 static chd_error map_read(chd_file *chd)
2313 {
2314         UINT32 entrysize = (chd->header.version < 3) ? OLD_MAP_ENTRY_SIZE : MAP_ENTRY_SIZE;
2315         UINT8 raw_map_entries[MAP_STACK_ENTRIES * MAP_ENTRY_SIZE];
2316         UINT64 fileoffset, maxoffset = 0;
2317         UINT8 cookie[MAP_ENTRY_SIZE];
2318         UINT32 count;
2319         chd_error err;
2320         int i;
2321
2322         /* first allocate memory */
2323         chd->map = (map_entry *)malloc(sizeof(chd->map[0]) * chd->header.totalhunks);
2324         if (!chd->map)
2325                 return CHDERR_OUT_OF_MEMORY;
2326
2327         /* read the map entries in in chunks and extract to the map list */
2328         fileoffset = chd->header.length;
2329         for (i = 0; i < chd->header.totalhunks; i += MAP_STACK_ENTRIES)
2330         {
2331                 /* compute how many entries this time */
2332                 int entries = chd->header.totalhunks - i, j;
2333                 if (entries > MAP_STACK_ENTRIES)
2334                         entries = MAP_STACK_ENTRIES;
2335
2336                 /* read that many */
2337                 core_fseek(chd->file, fileoffset, SEEK_SET);
2338                 count = core_fread(chd->file, raw_map_entries, entries * entrysize);
2339                 if (count != entries * entrysize)
2340                 {
2341                         err = CHDERR_READ_ERROR;
2342                         goto cleanup;
2343                 }
2344                 fileoffset += entries * entrysize;
2345
2346                 /* process that many */
2347                 if (entrysize == MAP_ENTRY_SIZE)
2348                 {
2349                         for (j = 0; j < entries; j++)
2350                                 map_extract(&raw_map_entries[j * MAP_ENTRY_SIZE], &chd->map[i + j]);
2351                 }
2352                 else
2353                 {
2354                         for (j = 0; j < entries; j++)
2355                                 map_extract_old(&raw_map_entries[j * OLD_MAP_ENTRY_SIZE], &chd->map[i + j], chd->header.hunkbytes);
2356                 }
2357
2358                 /* track the maximum offset */
2359                 for (j = 0; j < entries; j++)
2360                         if ((chd->map[i + j].flags & MAP_ENTRY_FLAG_TYPE_MASK) == V34_MAP_ENTRY_TYPE_COMPRESSED ||
2361                                 (chd->map[i + j].flags & MAP_ENTRY_FLAG_TYPE_MASK) == V34_MAP_ENTRY_TYPE_UNCOMPRESSED)
2362                                 maxoffset = MAX(maxoffset, chd->map[i + j].offset + chd->map[i + j].length);
2363         }
2364
2365         /* verify the cookie */
2366         core_fseek(chd->file, fileoffset, SEEK_SET);
2367         count = core_fread(chd->file, &cookie, entrysize);
2368         if (count != entrysize || memcmp(&cookie, END_OF_LIST_COOKIE, entrysize))
2369         {
2370                 err = CHDERR_INVALID_FILE;
2371                 goto cleanup;
2372         }
2373
2374         /* verify the length */
2375         if (maxoffset > core_fsize(chd->file))
2376         {
2377                 err = CHDERR_INVALID_FILE;
2378                 goto cleanup;
2379         }
2380         return CHDERR_NONE;
2381
2382 cleanup:
2383         if (chd->map)
2384                 free(chd->map);
2385         chd->map = NULL;
2386         return err;
2387 }
2388
2389 /***************************************************************************
2390     INTERNAL METADATA ACCESS
2391 ***************************************************************************/
2392
2393 /*-------------------------------------------------
2394     metadata_find_entry - find a metadata entry
2395 -------------------------------------------------*/
2396
2397 static chd_error metadata_find_entry(chd_file *chd, UINT32 metatag, UINT32 metaindex, metadata_entry *metaentry)
2398 {
2399         /* start at the beginning */
2400         metaentry->offset = chd->header.metaoffset;
2401         metaentry->prev = 0;
2402
2403         /* loop until we run out of options */
2404         while (metaentry->offset != 0)
2405         {
2406                 UINT8   raw_meta_header[METADATA_HEADER_SIZE];
2407                 UINT32  count;
2408
2409                 /* read the raw header */
2410                 core_fseek(chd->file, metaentry->offset, SEEK_SET);
2411                 count = core_fread(chd->file, raw_meta_header, sizeof(raw_meta_header));
2412                 if (count != sizeof(raw_meta_header))
2413                         break;
2414
2415                 /* extract the data */
2416                 metaentry->metatag = get_bigendian_uint32(&raw_meta_header[0]);
2417                 metaentry->length = get_bigendian_uint32(&raw_meta_header[4]);
2418                 metaentry->next = get_bigendian_uint64(&raw_meta_header[8]);
2419
2420                 /* flags are encoded in the high byte of length */
2421                 metaentry->flags = metaentry->length >> 24;
2422                 metaentry->length &= 0x00ffffff;
2423
2424                 /* if we got a match, proceed */
2425                 if (metatag == CHDMETATAG_WILDCARD || metaentry->metatag == metatag)
2426                         if (metaindex-- == 0)
2427                                 return CHDERR_NONE;
2428
2429                 /* no match, fetch the next link */
2430                 metaentry->prev = metaentry->offset;
2431                 metaentry->offset = metaentry->next;
2432         }
2433
2434         /* if we get here, we didn't find it */
2435         return CHDERR_METADATA_NOT_FOUND;
2436 }
2437
2438 /***************************************************************************
2439     ZLIB COMPRESSION CODEC
2440 ***************************************************************************/
2441
2442 /*-------------------------------------------------
2443     zlib_codec_init - initialize the ZLIB codec
2444 -------------------------------------------------*/
2445
2446 static chd_error zlib_codec_init(void *codec, uint32_t hunkbytes)
2447 {
2448         zlib_codec_data *data = (zlib_codec_data*)codec;
2449         chd_error err;
2450         int zerr;
2451
2452         /* clear the buffers */
2453         memset(data, 0, sizeof(zlib_codec_data));
2454
2455         /* init the inflater first */
2456         data->inflater.next_in = (Bytef *)data; /* bogus, but that's ok */
2457         data->inflater.avail_in = 0;
2458         data->inflater.zalloc = zlib_fast_alloc;
2459         data->inflater.zfree = zlib_fast_free;
2460         data->inflater.opaque = &data->allocator;
2461         zerr = inflateInit2(&data->inflater, -MAX_WBITS);
2462
2463         /* convert errors */
2464         if (zerr == Z_MEM_ERROR)
2465                 err = CHDERR_OUT_OF_MEMORY;
2466         else if (zerr != Z_OK)
2467                 err = CHDERR_CODEC_ERROR;
2468         else
2469                 err = CHDERR_NONE;
2470
2471         /* handle an error */
2472         if (err != CHDERR_NONE)
2473                 free(data);
2474
2475         return err;
2476 }
2477
2478 /*-------------------------------------------------
2479     zlib_codec_free - free data for the ZLIB
2480     codec
2481 -------------------------------------------------*/
2482
2483 static void zlib_codec_free(void *codec)
2484 {
2485         zlib_codec_data *data = (zlib_codec_data *)codec;
2486
2487         /* deinit the streams */
2488         if (data != NULL)
2489         {
2490                 int i;
2491
2492                 inflateEnd(&data->inflater);
2493
2494                 /* free our fast memory */
2495                 zlib_allocator_free(&data->allocator);
2496         }
2497 }
2498
2499 /*-------------------------------------------------
2500     zlib_codec_decompress - decompress data using
2501     the ZLIB codec
2502 -------------------------------------------------*/
2503
2504 static chd_error zlib_codec_decompress(void *codec, const uint8_t *src, uint32_t complen, uint8_t *dest, uint32_t destlen)
2505 {
2506         zlib_codec_data *data = (zlib_codec_data *)codec;
2507         int zerr;
2508
2509         /* reset the decompressor */
2510         data->inflater.next_in = (Bytef *)src;
2511         data->inflater.avail_in = complen;
2512         data->inflater.total_in = 0;
2513         data->inflater.next_out = (Bytef *)dest;
2514         data->inflater.avail_out = destlen;
2515         data->inflater.total_out = 0;
2516         zerr = inflateReset(&data->inflater);
2517         if (zerr != Z_OK)
2518                 return CHDERR_DECOMPRESSION_ERROR;
2519
2520         /* do it */
2521         zerr = inflate(&data->inflater, Z_FINISH);
2522         if (data->inflater.total_out != destlen)
2523                 return CHDERR_DECOMPRESSION_ERROR;
2524
2525         return CHDERR_NONE;
2526 }
2527
2528 /*-------------------------------------------------
2529     zlib_fast_alloc - fast malloc for ZLIB, which
2530     allocates and frees memory frequently
2531 -------------------------------------------------*/
2532 #define ZLIB_MIN_ALIGNMENT_BITS 512
2533 #define ZLIB_MIN_ALIGNMENT_BYTES (ZLIB_MIN_ALIGNMENT_BITS / 8)
2534
2535 static voidpf zlib_fast_alloc(voidpf opaque, uInt items, uInt size)
2536 {
2537         zlib_allocator *alloc = (zlib_allocator *)opaque;
2538         uintptr_t paddr = 0;
2539         UINT32 *ptr;
2540         int i;
2541
2542         /* compute the size, rounding to the nearest 1k */
2543         size = (size * items + 0x3ff) & ~0x3ff;
2544
2545         /* reuse a hunk if we can */
2546         for (i = 0; i < MAX_ZLIB_ALLOCS; i++)
2547         {
2548                 ptr = alloc->allocptr[i];
2549                 if (ptr && size == *ptr)
2550                 {
2551                         /* set the low bit of the size so we don't match next time */
2552                         *ptr |= 1;
2553                         return (voidpf)(alloc->allocptr2[i]);
2554                 }
2555         }
2556
2557         /* alloc a new one */
2558     ptr = (UINT32 *)malloc(size + sizeof(UINT32) + ZLIB_MIN_ALIGNMENT_BYTES);
2559         if (!ptr)
2560                 return NULL;
2561
2562         /* put it into the list */
2563         for (i = 0; i < MAX_ZLIB_ALLOCS; i++)
2564                 if (!alloc->allocptr[i])
2565                 {
2566                         alloc->allocptr[i] = ptr;
2567                         paddr = (((uintptr_t)ptr) + sizeof(UINT32) + (ZLIB_MIN_ALIGNMENT_BYTES-1)) & (~(ZLIB_MIN_ALIGNMENT_BYTES-1));
2568                         alloc->allocptr2[i] = (uint32_t*)paddr;
2569                         break;
2570                 }
2571
2572         /* set the low bit of the size so we don't match next time */
2573         *ptr = size | 1;
2574         return (voidpf)paddr;
2575 }
2576
2577 /*-------------------------------------------------
2578     zlib_fast_free - fast free for ZLIB, which
2579     allocates and frees memory frequently
2580 -------------------------------------------------*/
2581
2582 static void zlib_fast_free(voidpf opaque, voidpf address)
2583 {
2584         zlib_allocator *alloc = (zlib_allocator *)opaque;
2585         UINT32 *ptr = (UINT32 *)address;
2586         int i;
2587
2588         /* find the hunk */
2589         for (i = 0; i < MAX_ZLIB_ALLOCS; i++)
2590                 if (ptr == alloc->allocptr2[i])
2591                 {
2592                         /* clear the low bit of the size to allow matches */
2593                         *(alloc->allocptr[i]) &= ~1;
2594                         return;
2595                 }
2596 }
2597
2598 /*-------------------------------------------------
2599     zlib_allocator_free
2600 -------------------------------------------------*/
2601 static void zlib_allocator_free(voidpf opaque)
2602 {
2603         zlib_allocator *alloc = (zlib_allocator *)opaque;
2604         int i;
2605
2606         for (i = 0; i < MAX_ZLIB_ALLOCS; i++)
2607                 if (alloc->allocptr[i])
2608                         free(alloc->allocptr[i]);
2609 }