i386/libsaio/hfs.c

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