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