i386/libsaio/hfs.c

   1 /*
   2  * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
   3  *
   4  * @APPLE_LICENSE_HEADER_START@
   5  *
   6  * The contents of this file constitute Original Code as defined in and
   7  * are subject to the Apple Public Source License Version 1.1 (the
   8  * "License").  You may not use this file except in compliance with the
   9  * License.  Please obtain a copy of the License at
  10  * http://www.apple.com/publicsource and read it before using this file.
  11  *
  12  * This Original Code and all software distributed under the License are
  13  * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  14  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  15  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  16  * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT.  Please see the
  17  * License for the specific language governing rights and limitations
  18  * under the License.
  19  *
  20  * @APPLE_LICENSE_HEADER_END@
  21  */
  22 /*
  23  *  hfs.c - File System Module for HFS and HFS+.
  24  *
  25  *  Copyright (c) 1999-2002 Apple Computer, Inc.
  26  *
  27  *  DRI: Josh de Cesare
  28  */
  29
  30 #include <sl.h>
  31 #include <hfs/hfs_format.h>
  32
  33 #include "hfs.h"
  34
  35 #define kBlockSize (0x200)
  36
  37 #define kMDBBaseOffset (2 * kBlockSize)
  38
  39 #define kBTreeCatalog (0)
  40 #define kBTreeExtents (1)
  41
  42 #ifdef __i386__
  43
  44 static CICell                  gCurrentIH;
  45 static long long               gAllocationOffset;
  46 static long                    gIsHFSPlus;
  47 static long                    gBlockSize;
  48 static long                    gCacheBlockSize;
  49 static char                    *gBTreeHeaderBuffer;
  50 static BTHeaderRec             *gBTHeaders[2];
  51 static char                    *gHFSMdbVib;
  52 static HFSMasterDirectoryBlock *gHFSMDB;
  53 static char                    *gHFSPlusHeader;
  54 static HFSPlusVolumeHeader     *gHFSPlus;
  55 static char                    *gLinkTemp;
  56 static char                    *gTempStr;
  57
  58 #else  /* !__i386__ */
  59
  60 static CICell                  gCurrentIH;
  61 static long long               gAllocationOffset;
  62 static long                    gIsHFSPlus;
  63 static long                    gBlockSize;
  64 static long                    gCacheBlockSize;
  65 static char                    gBTreeHeaderBuffer[512];
  66 static BTHeaderRec             *gBTHeaders[2];
  67 static char                    gHFSMdbVib[kBlockSize];
  68 static HFSMasterDirectoryBlock *gHFSMDB =(HFSMasterDirectoryBlock*)gHFSMdbVib;
  69 static char                    gHFSPlusHeader[kBlockSize];
  70 static HFSPlusVolumeHeader     *gHFSPlus =(HFSPlusVolumeHeader*)gHFSPlusHeader;
  71 static char                    gLinkTemp[64];
  72
  73 #endif /* !__i386__ */
  74
  75 static long ReadFile(void *file, long *length);
  76 static long GetCatalogEntryInfo(void *entry, long *flags, long *time);
  77 static long ResolvePathToCatalogEntry(char *filePath, long *flags,
  78                 void *entry, long dirID, long *dirIndex);
  79
  80 static long GetCatalogEntry(long *dirIndex, char **name,
  81                 long *flags, long *time);
  82 static long ReadCatalogEntry(char *fileName, long dirID, void *entry,
  83                 long *dirIndex);
  84 static long ReadExtentsEntry(long fileID, long startBlock, void *entry);
  85
  86 static long ReadBTreeEntry(long btree, void *key, char *entry, long *dirIndex);
  87 static void GetBTreeRecord(long index, char *nodeBuffer, long nodeSize,
  88                 char **key, char **data);
  89
  90 static long ReadExtent(char *extent, long extentSize, long extentFile,
  91                 long offset, long size, void *buffer, long cache);
  92
  93 static long GetExtentStart(void *extents, long index);
  94 static long GetExtentSize(void *extents, long index);
  95
  96 static long CompareHFSCatalogKeys(void *key, void *testKey);
  97 static long CompareHFSPlusCatalogKeys(void *key, void *testKey);
  98 static long CompareHFSExtentsKeys(void *key, void *testKey);
  99 static long CompareHFSPlusExtentsKeys(void *key, void *testKey);
 100
 101 extern long FastRelString(char *str1, char *str2);
 102 extern long FastUnicodeCompare(u_int16_t *uniStr1, u_int32_t len1,
 103                 u_int16_t *uniStr2, u_int32_t len2);
 104 extern void utf_encodestr(const u_int16_t *ucsp, int ucslen,
 105                 u_int8_t *utf8p, u_int32_t bufsize);
 106 extern void utf_decodestr(const u_int8_t *utf8p, u_int16_t *ucsp,
 107                 u_int16_t *ucslen, u_int32_t bufsize);
 108
 109
 110 long HFSInitPartition(CICell ih)
 111 {
 112     long extentSize, extentFile, nodeSize;
 113     void *extent;
 114
 115     if (ih == gCurrentIH) {
 116 #ifdef __i386__
 117         CacheInit(ih, gCacheBlockSize);
 118 #endif
 119         return 0;
 120     }
 121
 122 #ifdef __i386__
 123     if (!gTempStr) gTempStr = (char *)malloc(4096);
 124     if (!gLinkTemp) gLinkTemp = (char *)malloc(64);
 125     if (!gBTreeHeaderBuffer) gBTreeHeaderBuffer = (char *)malloc(512);
 126     if (!gHFSMdbVib) {
 127         gHFSMdbVib = (char *)malloc(kBlockSize);
 128         gHFSMDB = (HFSMasterDirectoryBlock *)gHFSMdbVib;
 129     }
 130     if (!gHFSPlusHeader) {
 131         gHFSPlusHeader = (char *)malloc(kBlockSize);
 132         gHFSPlus = (HFSPlusVolumeHeader *)gHFSPlusHeader;
 133     }
 134     if (!gTempStr || !gLinkTemp || !gBTreeHeaderBuffer ||
 135         !gHFSMdbVib || !gHFSPlusHeader) return -1;
 136 #endif /* __i386__ */
 137
 138     gAllocationOffset = 0;
 139     gIsHFSPlus = 0;
 140     gBTHeaders[0] = 0;
 141     gBTHeaders[1] = 0;
 142
 143     // Look for the HFS MDB
 144     Seek(ih, kMDBBaseOffset);
 145     Read(ih, (long)gHFSMdbVib, kBlockSize);
 146
 147     if ( SWAP_BE16(gHFSMDB->drSigWord) == kHFSSigWord ) {
 148         gAllocationOffset = SWAP_BE16(gHFSMDB->drAlBlSt) * kBlockSize;
 149
 150         // See if it is HFSPlus
 151         if (SWAP_BE16(gHFSMDB->drEmbedSigWord) != kHFSPlusSigWord) {
 152             // Normal HFS;
 153             gCacheBlockSize = gBlockSize = SWAP_BE32(gHFSMDB->drAlBlkSiz);
 154             CacheInit(ih, gCacheBlockSize);
 155             gCurrentIH = ih;
 156
 157             // Get the Catalog BTree node size.
 158             extent     = (HFSExtentDescriptor *)&gHFSMDB->drCTExtRec;
 159             extentSize = SWAP_BE32(gHFSMDB->drCTFlSize);
 160             extentFile = kHFSCatalogFileID;
 161             ReadExtent(extent, extentSize, extentFile, 0, 256,
 162                        gBTreeHeaderBuffer + kBTreeCatalog * 256, 0);
 163
 164             nodeSize = SWAP_BE16(((BTHeaderRec *)(gBTreeHeaderBuffer + kBTreeCatalog * 256 +
 165                                  sizeof(BTNodeDescriptor)))->nodeSize);
 166
 167             // If the BTree node size is larger than the block size, reset the cache.
 168             if (nodeSize > gBlockSize) {
 169                 gCacheBlockSize = nodeSize;
 170                 CacheInit(ih, gCacheBlockSize);
 171             }
 172
 173             return 0;
 174         }
 175
 176         // Calculate the offset to the embeded HFSPlus volume.
 177         gAllocationOffset += (long long)SWAP_BE16(gHFSMDB->drEmbedExtent.startBlock) *
 178                                         SWAP_BE32(gHFSMDB->drAlBlkSiz);
 179     }
 180
 181     // Look for the HFSPlus Header
 182     Seek(ih, gAllocationOffset + kMDBBaseOffset);
 183     Read(ih, (long)gHFSPlusHeader, kBlockSize);
 184
 185     // Not a HFS[+] volume.
 186     if (SWAP_BE16(gHFSPlus->signature) != kHFSPlusSigWord) {
 187         verbose("HFS signature was not present.\n");
 188         return -1;
 189     }
 190
 191     gIsHFSPlus = 1;
 192     gCacheBlockSize = gBlockSize = SWAP_BE32(gHFSPlus->blockSize);
 193     CacheInit(ih, gCacheBlockSize);
 194     gCurrentIH = ih;
 195
 196     // Get the Catalog BTree node size.
 197     extent     = &gHFSPlus->catalogFile.extents;
 198     extentSize = SWAP_BE64(gHFSPlus->catalogFile.logicalSize);
 199     extentFile = kHFSCatalogFileID;
 200
 201     ReadExtent(extent, extentSize, extentFile, 0, 256,
 202                gBTreeHeaderBuffer + kBTreeCatalog * 256, 0);
 203
 204     nodeSize = SWAP_BE16(((BTHeaderRec *)(gBTreeHeaderBuffer + kBTreeCatalog * 256 +
 205                          sizeof(BTNodeDescriptor)))->nodeSize);
 206
 207     // If the BTree node size is larger than the block size, reset the cache.
 208     if (nodeSize > gBlockSize) {
 209         gCacheBlockSize = nodeSize;
 210         CacheInit(ih, gCacheBlockSize);
 211     }
 212
 213     return 0;
 214 }
 215
 216 long HFSLoadFile(CICell ih, char * filePath)
 217 {
 218     char entry[512];
 219     long dirID, result, length, flags;
 220
 221     verbose("Loading HFS%s file: [%s] from %x.\n",
 222             (gIsHFSPlus ? "+" : ""), filePath, ih);
 223
 224     if (HFSInitPartition(ih) == -1) return -1;
 225
 226     dirID = kHFSRootFolderID;
 227     // Skip a lead '\'.  Start in the system folder if there are two.
 228     if (filePath[0] == '/') {
 229         if (filePath[1] == '/') {
 230             if (gIsHFSPlus) dirID = SWAP_BE32(((long *)gHFSPlus->finderInfo)[5]);
 231             else dirID = SWAP_BE32(gHFSMDB->drFndrInfo[5]);
 232             if (dirID == 0) {
 233                 return -1;
 234             }
 235             filePath++;
 236         }
 237         filePath++;
 238     }
 239
 240     result = ResolvePathToCatalogEntry(filePath, &flags, entry, dirID, 0);
 241     if ((result == -1) || ((flags & kFileTypeMask) != kFileTypeFlat)) {
 242         return -1;
 243     }
 244
 245 #if 0 // Not yet for Intel. System.config/Default.table will fail this check.
 246     // Check file owner and permissions.
 247     if (flags & (kOwnerNotRoot | kPermGroupWrite | kPermOtherWrite)) return -1;
 248 #endif
 249
 250     result = ReadFile(entry, &length);
 251     if (result == -1) {
 252         return -1;
 253     }
 254
 255     return length;
 256 }
 257
 258 long HFSGetDirEntry(CICell ih, char * dirPath, long * dirIndex, char ** name,
 259                     long * flags, long * time)
 260 {
 261     char entry[512];
 262     long dirID, dirFlags;
 263
 264     if (HFSInitPartition(ih) == -1) return -1;
 265
 266     if (*dirIndex == -1) return -1;
 267
 268     dirID = kHFSRootFolderID;
 269     // Skip a lead '\'.  Start in the system folder if there are two.
 270     if (dirPath[0] == '/') {
 271         if (dirPath[1] == '/') {
 272             if (gIsHFSPlus) dirID = SWAP_BE32(((long *)gHFSPlus->finderInfo)[5]);
 273             else dirID = SWAP_BE32(gHFSMDB->drFndrInfo[5]);
 274             if (dirID == 0) return -1;
 275             dirPath++;
 276         }
 277         dirPath++;
 278     }
 279
 280     if (*dirIndex == 0) {
 281         ResolvePathToCatalogEntry(dirPath, &dirFlags, entry, dirID, dirIndex);
 282         if (*dirIndex == 0) *dirIndex = -1;
 283         if ((dirFlags & kFileTypeMask) != kFileTypeUnknown) return -1;
 284     }
 285
 286     GetCatalogEntry(dirIndex, name, flags, time);
 287     if (*dirIndex == 0) *dirIndex = -1;
 288     if ((*flags & kFileTypeMask) == kFileTypeUnknown) return -1;
 289
 290     return 0;
 291 }
 292
 293 // Private Functions
 294
 295 static long ReadFile(void * file, long * length)
 296 {
 297     void               *extents;
 298     long               fileID;
 299     HFSCatalogFile     *hfsFile     = file;
 300     HFSPlusCatalogFile *hfsPlusFile = file;
 301
 302     if (gIsHFSPlus) {
 303         fileID  = SWAP_BE32(hfsPlusFile->fileID);
 304         *length = SWAP_BE64(hfsPlusFile->dataFork.logicalSize);
 305         extents = &hfsPlusFile->dataFork.extents;
 306     } else {
 307         fileID  = SWAP_BE32(hfsFile->fileID);
 308         *length = SWAP_BE32(hfsFile->dataLogicalSize);
 309         extents = &hfsFile->dataExtents;
 310     }
 311
 312     if (*length > kLoadSize) {
 313         printf("File is too large.\n");
 314         return -1;
 315     }
 316
 317 #ifdef __i386__
 318     *length = ReadExtent((char *)extents, *length, fileID,
 319                          0, *length, (char *)gFSLoadAddress, 0);
 320 #else
 321     *length = ReadExtent((char *)extents, *length, fileID,
 322                          0, *length, (char *)kLoadAddr, 0);
 323 #endif
 324
 325     return 0;
 326 }
 327
 328 static long GetCatalogEntryInfo(void * entry, long * flags, long * time)
 329 {
 330     long tmpTime = 0;
 331
 332     // Get information about the file.
 333
 334     switch ( SWAP_BE16(*(short *)entry) )
 335     {
 336         case kHFSFolderRecord           :
 337             *flags = kFileTypeDirectory;
 338             tmpTime = SWAP_BE32(((HFSCatalogFolder *)entry)->modifyDate);
 339             break;
 340
 341         case kHFSPlusFolderRecord       :
 342             *flags = kFileTypeDirectory |
 343                      (SWAP_BE16(((HFSPlusCatalogFolder *)entry)->bsdInfo.fileMode) & kPermMask);
 344             if (SWAP_BE32(((HFSPlusCatalogFolder *)entry)->bsdInfo.ownerID) != 0)
 345                 *flags |= kOwnerNotRoot;
 346             tmpTime = SWAP_BE32(((HFSPlusCatalogFolder *)entry)->contentModDate);
 347             break;
 348
 349         case kHFSFileRecord             :
 350             *flags = kFileTypeFlat;
 351             tmpTime = SWAP_BE32(((HFSCatalogFile *)entry)->modifyDate);
 352             break;
 353
 354         case kHFSPlusFileRecord         :
 355             *flags = kFileTypeFlat |
 356                      (SWAP_BE16(((HFSPlusCatalogFile *)entry)->bsdInfo.fileMode) & kPermMask);
 357             if (SWAP_BE32(((HFSPlusCatalogFile *)entry)->bsdInfo.ownerID) != 0)
 358                 *flags |= kOwnerNotRoot;
 359             tmpTime = SWAP_BE32(((HFSPlusCatalogFile *)entry)->contentModDate);
 360             break;
 361
 362         case kHFSFileThreadRecord       :
 363         case kHFSPlusFileThreadRecord   :
 364         case kHFSFolderThreadRecord     :
 365         case kHFSPlusFolderThreadRecord :
 366             *flags = kFileTypeUnknown;
 367             tmpTime = 0;
 368             break;
 369     }
 370
 371     if (time != 0) {
 372         // Convert base time from 1904 to 1970.
 373         *time = tmpTime - 2082844800;
 374     }
 375
 376     return 0;
 377 }
 378
 379 static long ResolvePathToCatalogEntry(char * filePath, long * flags,
 380                                       void * entry, long dirID, long * dirIndex)
 381 {
 382     char                 *restPath;
 383     long                 result, cnt, subFolderID, tmpDirIndex;
 384     HFSPlusCatalogFile   *hfsPlusFile;
 385
 386     // Copy the file name to gTempStr
 387     cnt = 0;
 388     while ((filePath[cnt] != '/') && (filePath[cnt] != '\0')) cnt++;
 389     strlcpy(gTempStr, filePath, cnt+1);
 390
 391     // Move restPath to the right place.
 392     if (filePath[cnt] != '\0') cnt++;
 393     restPath = filePath + cnt;
 394
 395     // gTempStr is a name in the current Dir.
 396     // restPath is the rest of the path if any.
 397
 398     result = ReadCatalogEntry(gTempStr, dirID, entry, dirIndex);
 399     if (result == -1) {
 400         return -1;
 401     }
 402
 403     GetCatalogEntryInfo(entry, flags, 0);
 404
 405     if ((*flags & kFileTypeMask) == kFileTypeDirectory) {
 406         if (gIsHFSPlus)
 407             subFolderID = SWAP_BE32(((HFSPlusCatalogFolder *)entry)->folderID);
 408         else
 409             subFolderID = SWAP_BE32(((HFSCatalogFolder *)entry)->folderID);
 410
 411         result = ResolvePathToCatalogEntry(restPath, flags, entry,
 412                                            subFolderID, dirIndex);
 413     }
 414
 415     if (gIsHFSPlus && ((*flags & kFileTypeMask) == kFileTypeFlat)) {
 416         hfsPlusFile = (HFSPlusCatalogFile *)entry;
 417         if ((SWAP_BE32(hfsPlusFile->userInfo.fdType) == kHardLinkFileType) &&
 418             (SWAP_BE32(hfsPlusFile->userInfo.fdCreator) == kHFSPlusCreator)) {
 419                 sprintf(gLinkTemp, "%s/%s%ld", HFSPLUSMETADATAFOLDER,
 420                         HFS_INODE_PREFIX, SWAP_BE32(hfsPlusFile->bsdInfo.special.iNodeNum));
 421                 result = ResolvePathToCatalogEntry(gLinkTemp, flags, entry,
 422                                                    kHFSRootFolderID, &tmpDirIndex);
 423         }
 424     }
 425
 426     return result;
 427 }
 428
 429 static long GetCatalogEntry(long * dirIndex, char ** name,
 430                             long * flags, long * time)
 431 {
 432     long              extentSize, nodeSize, curNode, index;
 433     void              *extent;
 434     char              *nodeBuf, *testKey, *entry;
 435     BTNodeDescriptor  *node;
 436
 437     if (gIsHFSPlus) {
 438         extent     = &gHFSPlus->catalogFile.extents;
 439         extentSize = SWAP_BE64(gHFSPlus->catalogFile.logicalSize);
 440     } else {
 441         extent     = (HFSExtentDescriptor *)&gHFSMDB->drCTExtRec;
 442         extentSize = SWAP_BE32(gHFSMDB->drCTFlSize);
 443     }
 444
 445     nodeSize = SWAP_BE16(gBTHeaders[kBTreeCatalog]->nodeSize);
 446     nodeBuf  = (char *)malloc(nodeSize);
 447     node     = (BTNodeDescriptor *)nodeBuf;
 448
 449     index   = *dirIndex % nodeSize;
 450     curNode = *dirIndex / nodeSize;
 451
 452     // Read the BTree node and get the record for index.
 453     ReadExtent(extent, extentSize, kHFSCatalogFileID,
 454                curNode * nodeSize, nodeSize, nodeBuf, 1);
 455     GetBTreeRecord(index, nodeBuf, nodeSize, &testKey, &entry);
 456
 457     GetCatalogEntryInfo(entry, flags, time);
 458
 459     // Get the file name.
 460     if (gIsHFSPlus) {
 461         utf_encodestr(((HFSPlusCatalogKey *)testKey)->nodeName.unicode,
 462                       SWAP_BE16(((HFSPlusCatalogKey *)testKey)->nodeName.length),
 463                       gTempStr, 256);
 464     } else {
 465         strncpy(gTempStr,
 466                 &((HFSCatalogKey *)testKey)->nodeName[1],
 467                  ((HFSCatalogKey *)testKey)->nodeName[0]);
 468     }
 469     *name = gTempStr;
 470
 471     // Update dirIndex.
 472     index++;
 473     if (index == SWAP_BE16(node->numRecords)) {
 474         index = 0;
 475         curNode = SWAP_BE32(node->fLink);
 476     }
 477     *dirIndex = curNode * nodeSize + index;
 478
 479     free(nodeBuf);
 480
 481     return 0;
 482 }
 483
 484 static long ReadCatalogEntry(char * fileName, long dirID,
 485                              void * entry,    long * dirIndex)
 486 {
 487     long              length;
 488     char              key[sizeof(HFSPlusCatalogKey)];
 489     HFSCatalogKey     *hfsKey     = (HFSCatalogKey *)key;
 490     HFSPlusCatalogKey *hfsPlusKey = (HFSPlusCatalogKey *)key;
 491
 492     // Make the catalog key.
 493     if ( gIsHFSPlus )
 494     {
 495         hfsPlusKey->parentID = SWAP_BE32(dirID);
 496         length = strlen(fileName);
 497         if (length > 255) length = 255;
 498         utf_decodestr(fileName, hfsPlusKey->nodeName.unicode,
 499                       &(hfsPlusKey->nodeName.length), 512);
 500     } else {
 501         hfsKey->parentID = SWAP_BE32(dirID);
 502         length = strlen(fileName);
 503         if (length > 31) length = 31;
 504         hfsKey->nodeName[0] = length;
 505         strncpy(hfsKey->nodeName + 1, fileName, length);
 506     }
 507
 508     return ReadBTreeEntry(kBTreeCatalog, &key, entry, dirIndex);
 509 }
 510
 511 static long ReadExtentsEntry(long fileID, long startBlock, void * entry)
 512 {
 513     char             key[sizeof(HFSPlusExtentKey)];
 514     HFSExtentKey     *hfsKey     = (HFSExtentKey *)key;
 515     HFSPlusExtentKey *hfsPlusKey = (HFSPlusExtentKey *)key;
 516
 517     // Make the extents key.
 518     if (gIsHFSPlus) {
 519         hfsPlusKey->forkType   = 0;
 520         hfsPlusKey->fileID     = SWAP_BE32(fileID);
 521         hfsPlusKey->startBlock = SWAP_BE32(startBlock);
 522     } else {
 523         hfsKey->forkType   = 0;
 524         hfsKey->fileID     = SWAP_BE32(fileID);
 525         hfsKey->startBlock = SWAP_BE16(startBlock);
 526     }
 527
 528     return ReadBTreeEntry(kBTreeExtents, &key, entry, 0);
 529 }
 530
 531 static long ReadBTreeEntry(long btree, void * key, char * entry, long * dirIndex)
 532 {
 533     long             extentSize;
 534     void             *extent;
 535     short            extentFile;
 536     char             *nodeBuf;
 537     BTNodeDescriptor *node;
 538     long             nodeSize, result = 0, entrySize = 0;
 539     long             curNode, index = 0, lowerBound, upperBound;
 540     char             *testKey, *recordData;
 541
 542     // Figure out which tree is being looked at.
 543     if (btree == kBTreeCatalog) {
 544         if (gIsHFSPlus) {
 545             extent     = &gHFSPlus->catalogFile.extents;
 546             extentSize = SWAP_BE64(gHFSPlus->catalogFile.logicalSize);
 547         } else {
 548             extent     = (HFSExtentDescriptor *)&gHFSMDB->drCTExtRec;
 549             extentSize = SWAP_BE32(gHFSMDB->drCTFlSize);
 550         }
 551         extentFile = kHFSCatalogFileID;
 552     } else {
 553         if (gIsHFSPlus) {
 554             extent     = &gHFSPlus->extentsFile.extents;
 555             extentSize = SWAP_BE64(gHFSPlus->extentsFile.logicalSize);
 556         } else {
 557             extent     = (HFSExtentDescriptor *)&gHFSMDB->drXTExtRec;
 558             extentSize = SWAP_BE32(gHFSMDB->drXTFlSize);
 559         }
 560         extentFile = kHFSExtentsFileID;
 561     }
 562
 563     // Read the BTree Header if needed.
 564     if (gBTHeaders[btree] == 0) {
 565         ReadExtent(extent, extentSize, extentFile, 0, 256,
 566                    gBTreeHeaderBuffer + btree * 256, 0);
 567         gBTHeaders[btree] = (BTHeaderRec *)(gBTreeHeaderBuffer + btree * 256 +
 568                                             sizeof(BTNodeDescriptor));
 569     }
 570
 571     curNode  = SWAP_BE32(gBTHeaders[btree]->rootNode);
 572     nodeSize = SWAP_BE16(gBTHeaders[btree]->nodeSize);
 573     nodeBuf  = (char *)malloc(nodeSize);
 574     node     = (BTNodeDescriptor *)nodeBuf;
 575
 576     while (1) {
 577         // Read the current node.
 578         ReadExtent(extent, extentSize, extentFile,
 579                    curNode * nodeSize, nodeSize, nodeBuf, 1);
 580
 581         // Find the matching key.
 582         lowerBound = 0;
 583         upperBound = SWAP_BE16(node->numRecords) - 1;
 584         while (lowerBound <= upperBound) {
 585             index = (lowerBound + upperBound) / 2;
 586
 587             GetBTreeRecord(index, nodeBuf, nodeSize, &testKey, &recordData);
 588
 589             if (gIsHFSPlus) {
 590                 if (btree == kBTreeCatalog) {
 591                     result = CompareHFSPlusCatalogKeys(key, testKey);
 592                 } else {
 593                     result = CompareHFSPlusExtentsKeys(key, testKey);
 594                 }
 595             } else {
 596                 if (btree == kBTreeCatalog) {
 597                     result = CompareHFSCatalogKeys(key, testKey);
 598                 } else {
 599                     result = CompareHFSExtentsKeys(key, testKey);
 600                 }
 601             }
 602
 603             if (result < 0) upperBound = index - 1;        // search < trial
 604             else if (result > 0) lowerBound = index + 1;   // search > trial
 605             else break;                                    // search = trial
 606         }
 607
 608         if (result < 0) {
 609             index = upperBound;
 610             GetBTreeRecord(index, nodeBuf, nodeSize, &testKey, &recordData);
 611         }
 612
 613         // Found the closest key... Recurse on it if this is an index node.
 614         if (node->kind == kBTIndexNode) {
 615             curNode = SWAP_BE32( *((long *)recordData) );
 616         } else break;
 617     }
 618
 619     // Return error if the file was not found.
 620     if (result != 0) { free(nodeBuf); return -1; }
 621
 622     if (btree == kBTreeCatalog) {
 623         switch (SWAP_BE16(*(short *)recordData)) {
 624             case kHFSFolderRecord           : entrySize = 70;  break;
 625             case kHFSFileRecord             : entrySize = 102; break;
 626             case kHFSFolderThreadRecord     : entrySize = 46;  break;
 627             case kHFSFileThreadRecord       : entrySize = 46;  break;
 628             case kHFSPlusFolderRecord       : entrySize = 88;  break;
 629             case kHFSPlusFileRecord         : entrySize = 248; break;
 630             case kHFSPlusFolderThreadRecord : entrySize = 264; break;
 631             case kHFSPlusFileThreadRecord   : entrySize = 264; break;
 632         }
 633     } else {
 634         if (gIsHFSPlus) entrySize = sizeof(HFSPlusExtentRecord);
 635         else entrySize = sizeof(HFSExtentRecord);
 636     }
 637
 638     bcopy(recordData, entry, entrySize);
 639
 640     // Update dirIndex.
 641     if (dirIndex != 0) {
 642         index++;
 643         if (index == SWAP_BE16(node->numRecords)) {
 644             index = 0;
 645             curNode = SWAP_BE32(node->fLink);
 646         }
 647         *dirIndex = curNode * nodeSize + index;
 648     }
 649
 650     free(nodeBuf);
 651
 652     return 0;
 653 }
 654
 655 static void GetBTreeRecord(long index, char * nodeBuffer, long nodeSize,
 656                            char ** key, char ** data)
 657 {
 658     long keySize;
 659     long recordOffset;
 660
 661     recordOffset = SWAP_BE16(*((short *)(nodeBuffer + (nodeSize - 2 * index - 2))));
 662     *key = nodeBuffer + recordOffset;
 663     if (gIsHFSPlus) {
 664         keySize = SWAP_BE16(*(short *)*key);
 665         *data = *key + 2 + keySize;
 666     } else {
 667         keySize = **key;
 668         *data = *key + 2 + keySize - (keySize & 1);
 669     }
 670 }
 671
 672 static long ReadExtent(char * extent, long extentSize,
 673                        long extentFile, long offset, long size,
 674                        void * buffer, long cache)
 675 {
 676     long      lastOffset, blockNumber, countedBlocks = 0;
 677     long      nextExtent = 0, sizeRead = 0, readSize;
 678     long      nextExtentBlock, currentExtentBlock = 0;
 679     long long readOffset;
 680     long      extentDensity, sizeofExtent, currentExtentSize;
 681     char      *currentExtent, *extentBuffer = 0, *bufferPos = buffer;
 682
 683     if (offset >= extentSize) return 0;
 684
 685     if (gIsHFSPlus) {
 686         extentDensity = kHFSPlusExtentDensity;
 687         sizeofExtent  = sizeof(HFSPlusExtentDescriptor);
 688     } else {
 689         extentDensity = kHFSExtentDensity;
 690         sizeofExtent  = sizeof(HFSExtentDescriptor);
 691     }
 692
 693     lastOffset = offset + size;
 694     while (offset < lastOffset) {
 695         blockNumber = offset / gBlockSize;
 696
 697         // Find the extent for the offset.
 698         for (; ; nextExtent++) {
 699             if (nextExtent < extentDensity) {
 700                 if ((countedBlocks+GetExtentSize(extent, nextExtent)-1)<blockNumber) {
 701                     countedBlocks += GetExtentSize(extent, nextExtent);
 702                     continue;
 703                 }
 704
 705                 currentExtent = extent + nextExtent * sizeofExtent;
 706                 break;
 707             }
 708
 709             if (extentBuffer == 0) {
 710                 extentBuffer = malloc(sizeofExtent * extentDensity);
 711                 if (extentBuffer == 0) return -1;
 712             }
 713
 714             nextExtentBlock = nextExtent / extentDensity;
 715             if (currentExtentBlock != nextExtentBlock) {
 716                 ReadExtentsEntry(extentFile, countedBlocks, extentBuffer);
 717                 currentExtentBlock = nextExtentBlock;
 718             }
 719
 720             currentExtentSize = GetExtentSize(extentBuffer, nextExtent % extentDensity);
 721
 722             if ((countedBlocks + currentExtentSize - 1) >= blockNumber) {
 723                 currentExtent = extentBuffer + sizeofExtent * (nextExtent % extentDensity);
 724                 break;
 725             }
 726
 727             countedBlocks += currentExtentSize;
 728         }
 729
 730         readOffset = ((blockNumber - countedBlocks) * gBlockSize) +
 731                      (offset % gBlockSize);
 732
 733         readSize = GetExtentSize(currentExtent, 0) * gBlockSize - readOffset;
 734         if (readSize > (size - sizeRead)) readSize = size - sizeRead;
 735
 736         readOffset += (long long)GetExtentStart(currentExtent, 0) * gBlockSize;
 737
 738         CacheRead(gCurrentIH, bufferPos, gAllocationOffset + readOffset,
 739                   readSize, cache);
 740
 741         sizeRead += readSize;
 742         offset += readSize;
 743         bufferPos += readSize;
 744     }
 745
 746     if (extentBuffer) free(extentBuffer);
 747
 748     return sizeRead;
 749 }
 750
 751 static long GetExtentStart(void * extents, long index)
 752 {
 753     long                    start;
 754     HFSExtentDescriptor     *hfsExtents     = extents;
 755     HFSPlusExtentDescriptor *hfsPlusExtents = extents;
 756
 757     if (gIsHFSPlus) start = SWAP_BE32(hfsPlusExtents[index].startBlock);
 758     else start = SWAP_BE16(hfsExtents[index].startBlock);
 759
 760     return start;
 761 }
 762
 763 static long GetExtentSize(void * extents, long index)
 764 {
 765     long                    size;
 766     HFSExtentDescriptor     *hfsExtents     = extents;
 767     HFSPlusExtentDescriptor *hfsPlusExtents = extents;
 768
 769     if (gIsHFSPlus) size = SWAP_BE32(hfsPlusExtents[index].blockCount);
 770     else size = SWAP_BE16(hfsExtents[index].blockCount);
 771
 772     return size;
 773 }
 774
 775 static long CompareHFSCatalogKeys(void * key, void * testKey)
 776 {
 777     HFSCatalogKey *searchKey, *trialKey;
 778     long          result, searchParentID, trialParentID;
 779
 780     searchKey = key;
 781     trialKey  = testKey;
 782
 783     searchParentID = SWAP_BE32(searchKey->parentID);
 784     trialParentID  = SWAP_BE32(trialKey->parentID);
 785
 786     // parent dirID is unsigned
 787     if (searchParentID > trialParentID)      result = 1;
 788     else if (searchParentID < trialParentID) result = -1;
 789     else {
 790         // parent dirID's are equal, compare names
 791         result = FastRelString(searchKey->nodeName, trialKey->nodeName);
 792     }
 793
 794     return result;
 795 }
 796
 797 static long CompareHFSPlusCatalogKeys(void * key, void * testKey)
 798 {
 799     HFSPlusCatalogKey *searchKey, *trialKey;
 800     long              result, searchParentID, trialParentID;
 801
 802     searchKey = key;
 803     trialKey  = testKey;
 804
 805     searchParentID = SWAP_BE32(searchKey->parentID);
 806     trialParentID  = SWAP_BE32(trialKey->parentID);
 807
 808     // parent dirID is unsigned
 809     if (searchParentID > trialParentID)      result = 1;
 810     else if (searchParentID < trialParentID) result = -1;
 811     else {
 812         // parent dirID's are equal, compare names
 813         if ((searchKey->nodeName.length == 0) || (trialKey->nodeName.length == 0))
 814             result = searchKey->nodeName.length - trialKey->nodeName.length;
 815         else
 816             result = FastUnicodeCompare(&searchKey->nodeName.unicode[0],
 817                                         SWAP_BE16(searchKey->nodeName.length),
 818                                         &trialKey->nodeName.unicode[0],
 819                                         SWAP_BE16(trialKey->nodeName.length));
 820     }
 821
 822     return result;
 823 }
 824
 825 static long CompareHFSExtentsKeys(void * key, void * testKey)
 826 {
 827     HFSExtentKey *searchKey, *trialKey;
 828     long         result;
 829
 830     searchKey = key;
 831     trialKey  = testKey;
 832
 833     // assume searchKey < trialKey
 834     result = -1;
 835
 836     if (searchKey->fileID == trialKey->fileID) {
 837         // FileNum's are equal; compare fork types
 838         if (searchKey->forkType == trialKey->forkType) {
 839             // Fork types are equal; compare allocation block number
 840             if (searchKey->startBlock == trialKey->startBlock) {
 841                 // Everything is equal
 842                 result = 0;
 843             } else {
 844                 // Allocation block numbers differ; determine sign
 845                 if (SWAP_BE16(searchKey->startBlock) > SWAP_BE16(trialKey->startBlock))
 846                     result = 1;
 847             }
 848         } else {
 849             // Fork types differ; determine sign
 850             if (searchKey->forkType > trialKey->forkType) result = 1;
 851         }
 852     } else {
 853         // FileNums differ; determine sign
 854         if (SWAP_BE32(searchKey->fileID) > SWAP_BE32(trialKey->fileID))
 855             result = 1;
 856     }
 857
 858     return result;
 859 }
 860
 861 static long CompareHFSPlusExtentsKeys(void * key, void * testKey)
 862 {
 863     HFSPlusExtentKey *searchKey, *trialKey;
 864     long             result;
 865
 866     searchKey = key;
 867     trialKey  = testKey;
 868
 869     // assume searchKey < trialKey
 870     result = -1;
 871
 872     if (searchKey->fileID == trialKey->fileID) {
 873         // FileNum's are equal; compare fork types
 874         if (searchKey->forkType == trialKey->forkType) {
 875             // Fork types are equal; compare allocation block number
 876             if (searchKey->startBlock == trialKey->startBlock) {
 877                 // Everything is equal
 878                 result = 0;
 879             } else {
 880                 // Allocation block numbers differ; determine sign
 881                 if (SWAP_BE32(searchKey->startBlock) > SWAP_BE32(trialKey->startBlock))
 882                     result = 1;
 883             }
 884         } else {
 885             // Fork types differ; determine sign
 886             if (searchKey->forkType > trialKey->forkType) result = 1;
 887         }
 888     } else {
 889         // FileNums differ; determine sign
 890         if (SWAP_BE32(searchKey->fileID) > SWAP_BE32(trialKey->fileID))
 891             result = 1;
 892     }
 893
 894     return result;
 895 }