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