bootx.tproj/fs.subproj/hfs.c

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