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