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