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-2000 Apple Computer, Inc.
  26  *
  27  *  DRI: Josh de Cesare
  28  */
  29
  30 #include <sl.h>
  31
  32 #if kMacOSXServer
  33 #define _LONG_LONG
  34 #include <bsd/hfs/hfscommon/headers/HFSBtreesPriv.h>
  35 #include <bsd/hfs/hfscommon/headers/system/MacOSTypes.h>
  36 #include <bsd/hfs/hfscommon/headers/system/MacOSStubs.h>
  37 #include <bsd/hfs/hfscommon/headers/HFSVolumes.h>
  38 #define kBTIndexNode kIndexNode
  39 #define BTHeaderRec HeaderRec
  40 #define GetNodeType(node) (node->type)
  41 #else
  42 #define GetNodeType(node) (node->kind)
  43 #include <bsd/hfs/hfs_format.h>
  44 #endif
  45
  46
  47
  48 #define kBlockSize (0x200)
  49
  50 #define kMDBBaseOffset (2 * kBlockSize)
  51
  52 #define kBTreeCatalog (0)
  53 #define kBTreeExtents (1)
  54
  55 static CICell                  gCurrentIH;
  56 static long long               gAllocationOffset;
  57 static long                    gIsHFSPlus;
  58 static long                    gBlockSize;
  59 static char                    gBTreeHeaderBuffer[512];
  60 static BTHeaderRec             *gBTHeaders[2];
  61 static char                    gHFSMdbVib[kBlockSize];
  62 static HFSMasterDirectoryBlock *gHFSMDB =(HFSMasterDirectoryBlock*)gHFSMdbVib;
  63 static char                    gHFSPlusHeader[kBlockSize];
  64 static HFSPlusVolumeHeader     *gHFSPlus =(HFSPlusVolumeHeader*)gHFSPlusHeader;
  65 static char                    gLinkTemp[64];
  66
  67
  68 static long ReadFile(void *file, long *length);
  69 static long ResolvePathToCatalogEntry(char *filePath, long *flags,
  70                                       void *entry, long dirID, long *dirIndex);
  71
  72 static long GetCatalogEntry(long *dirIndex, char **name,
  73                             long *flags, long *time);
  74 static long ReadCatalogEntry(char *fileName, long dirID, void *entry,
  75                              long *dirIndex);
  76 static long ReadExtentsEntry(long fileID, long startBlock, void *entry);
  77
  78 static long ReadBTreeEntry(long btree, void *key, char *entry, long *dirIndex);
  79 static void GetBTreeRecord(long index, char *nodeBuffer, long nodeSize,
  80                            char **key, char **data);
  81
  82 static long ReadExtent(char *extent, long extentSize, long extentFile,
  83                        long offset, long size, void *buffer, long cache);
  84
  85 static long GetExtentStart(void *extents, long index);
  86 static long GetExtentSize(void *extents, long index);
  87
  88 static long CompareHFSCatalogKeys(void *key, void *testKey);
  89 static long CompareHFSPlusCatalogKeys(void *key, void *testKey);
  90 static long CompareHFSExtentsKeys(void *key, void *testKey);
  91 static long CompareHFSPlusExtentsKeys(void *key, void *testKey);
  92
  93 extern long FastRelString(char *str1, char *str2);
  94 extern long FastUnicodeCompare(u_int16_t *uniStr1, u_int32_t len1,
  95                                u_int16_t *uniStr2, u_int32_t len2);
  96 extern void utf_encodestr(const u_int16_t *ucsp, int ucslen,
  97                           u_int8_t *utf8p, u_int32_t bufsize);
  98 extern void utf_decodestr(const u_int8_t *utf8p, u_int16_t *ucsp,
  99                           u_int16_t *ucslen, u_int32_t bufsize);
 100
 101
 102 long HFSInitPartition(CICell ih)
 103 {
 104   long extentSize, extentFile, nodeSize;
 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   gBTHeaders[0] = 0;
 114   gBTHeaders[1] = 0;
 115
 116   // Look for the HFS MDB
 117   Seek(ih, kMDBBaseOffset);
 118   Read(ih, (long)gHFSMdbVib, kBlockSize);
 119
 120   if (gHFSMDB->drSigWord == kHFSSigWord) {
 121     gAllocationOffset = gHFSMDB->drAlBlSt * kBlockSize;
 122
 123     // See if it is HFSPlus
 124     if (gHFSMDB->drEmbedSigWord != kHFSPlusSigWord) {
 125       // Normal HFS;
 126       gBlockSize = gHFSMDB->drAlBlkSiz;
 127       CacheInit(ih, gBlockSize);
 128       gCurrentIH = ih;
 129
 130       // Get the Catalog BTree node size.
 131       extent     = (HFSExtentDescriptor *)&gHFSMDB->drCTExtRec;
 132       extentSize = gHFSMDB->drCTFlSize;
 133       extentFile = kHFSCatalogFileID;
 134       ReadExtent(extent, extentSize, extentFile, 0, 256,
 135                  gBTreeHeaderBuffer + kBTreeCatalog * 256, 0);
 136       nodeSize = ((BTHeaderRec *)(gBTreeHeaderBuffer + kBTreeCatalog * 256 + sizeof(BTNodeDescriptor)))->nodeSize;
 137
 138       // If the BTree node size is larger than the block size, reset the cache.
 139       if (nodeSize > gBlockSize) CacheInit(ih, nodeSize);
 140
 141       return 0;
 142     }
 143
 144     // Calculate the offset to the embeded HFSPlus volume.
 145     gAllocationOffset += (long long)gHFSMDB->drEmbedExtent.startBlock * gHFSMDB->drAlBlkSiz;
 146   }
 147
 148   // Look for the HFSPlus Header
 149   Seek(ih, gAllocationOffset + kMDBBaseOffset);
 150   Read(ih, (long)gHFSPlusHeader, kBlockSize);
 151
 152   // Not a HFS[+] volume.
 153   if (gHFSPlus->signature != kHFSPlusSigWord) return -1;
 154
 155   gIsHFSPlus = 1;
 156   gBlockSize = gHFSPlus->blockSize;
 157   CacheInit(ih, gBlockSize);
 158   gCurrentIH = ih;
 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   char entry[512];
 177   long dirID, result, length, flags;
 178
 179   if (HFSInitPartition(ih) == -1) return -1;
 180
 181   printf("Loading HFS%s file: [%s] from %x.\n",
 182          (gIsHFSPlus ? "+" : ""), filePath, ih);
 183
 184   dirID = kHFSRootFolderID;
 185   // Skip a lead '\'.  Start in the system folder if there are two.
 186   if (filePath[0] == '\\') {
 187     if (filePath[1] == '\\') {
 188       if (gIsHFSPlus) dirID = ((long *)gHFSPlus->finderInfo)[5];
 189       else dirID = gHFSMDB->drFndrInfo[5];
 190       if (dirID == 0) return -1;
 191       filePath++;
 192     }
 193     filePath++;
 194   }
 195
 196   result = ResolvePathToCatalogEntry(filePath, &flags, entry, dirID, 0);
 197   if ((result == -1) || (flags != kFlatFileType)) return -1;
 198
 199   result = ReadFile(entry, &length);
 200   if (result == -1) return -1;
 201
 202   return length;
 203 }
 204
 205 long HFSGetDirEntry(CICell ih, char *dirPath, long *dirIndex, char **name,
 206                     long *flags, long *time)
 207 {
 208   char entry[512];
 209   long dirID, dirFlags;
 210
 211   if (HFSInitPartition(ih) == -1) return -1;
 212
 213   if (*dirIndex == -1) return -1;
 214
 215   dirID = kHFSRootFolderID;
 216   // Skip a lead '\'.  Start in the system folder if there are two.
 217   if (dirPath[0] == '\\') {
 218     if (dirPath[1] == '\\') {
 219       if (gIsHFSPlus) dirID = ((long *)gHFSPlus->finderInfo)[5];
 220       else dirID = gHFSMDB->drFndrInfo[5];
 221       if (dirID == 0) return -1;
 222       dirPath++;
 223     }
 224     dirPath++;
 225   }
 226
 227   if (*dirIndex == 0) {
 228     ResolvePathToCatalogEntry(dirPath, &dirFlags, entry, dirID, dirIndex);
 229     if (*dirIndex == 0) *dirIndex = -1;
 230     if (dirFlags != kUnknownFileType) return -1;
 231   }
 232
 233   GetCatalogEntry(dirIndex, name, flags, time);
 234   if (*dirIndex == 0) *dirIndex = -1;
 235   if (*flags == kUnknownFileType) return -1;
 236
 237   return 0;
 238 }
 239
 240
 241 // Private Functions
 242
 243 static long ReadFile(void *file, long *length)
 244 {
 245   void               *extents;
 246   long               fileID;
 247   HFSCatalogFile     *hfsFile     = file;
 248   HFSPlusCatalogFile *hfsPlusFile = file;
 249
 250   if (gIsHFSPlus) {
 251     fileID  = hfsPlusFile->fileID;
 252     *length = hfsPlusFile->dataFork.logicalSize;
 253     extents = &hfsPlusFile->dataFork.extents;
 254   } else {
 255     fileID  = hfsFile->fileID;
 256     *length = hfsFile->dataLogicalSize;
 257     extents = &hfsFile->dataExtents;
 258   }
 259
 260   if (*length > kLoadSize) {
 261     printf("File is too large.\n");
 262     return -1;
 263   }
 264
 265   *length = ReadExtent((char *)extents, *length, fileID,
 266                        0, *length, (char *)kLoadAddr, 0);
 267
 268   return 0;
 269 }
 270
 271 static long ResolvePathToCatalogEntry(char *filePath, long *flags,
 272                                       void *entry, long dirID, long *dirIndex)
 273 {
 274   char                 *restPath;
 275   long                 result, cnt, subFolderID, tmpDirIndex;
 276   HFSCatalogFolder     *hfsFolder;
 277   HFSPlusCatalogFolder *hfsPlusFolder;
 278   HFSPlusCatalogFile   *hfsPlusFile;
 279
 280   hfsFolder     = (HFSCatalogFolder *)entry;
 281   hfsPlusFolder = (HFSPlusCatalogFolder *)entry;
 282
 283   // Copy the file name to gTempStr
 284   cnt = 0;
 285   while ((filePath[cnt] != '\\') && (filePath[cnt] != '\0')) cnt++;
 286   strncpy(gTempStr, filePath, cnt);
 287
 288   // Move restPath to the right place.
 289   if (filePath[cnt] != '\0') cnt++;
 290   restPath = filePath + cnt;
 291
 292   // gTempStr is a name in the current Dir.
 293   // restPath is the rest of the path if any.
 294
 295   result = ReadCatalogEntry(gTempStr, dirID, entry, dirIndex);
 296   if (result == -1) return -1;
 297
 298   if (gIsHFSPlus) {
 299     if (hfsPlusFolder->recordType == kHFSPlusFolderRecord) {
 300       *flags = kDirectoryFileType;
 301       subFolderID = hfsPlusFolder->folderID;
 302     } else if (hfsPlusFolder->recordType == kHFSPlusFileRecord) {
 303       *flags = kFlatFileType;
 304     } else if (hfsPlusFolder->recordType == kHFSPlusFolderThreadRecord) {
 305       *flags = kUnknownFileType;
 306     } else return -1;
 307   } else {
 308     if (hfsFolder->recordType == kHFSFolderRecord) {
 309       *flags = kDirectoryFileType;
 310       subFolderID = hfsFolder->folderID;
 311     } else if (hfsFolder->recordType == kHFSFileRecord) {
 312       *flags = kFlatFileType;
 313     } else if (hfsFolder->recordType == kHFSFolderThreadRecord) {
 314       *flags = kUnknownFileType;
 315     } else return -1;
 316   }
 317
 318   if (*flags == kDirectoryFileType)
 319     result = ResolvePathToCatalogEntry(restPath, flags, entry,
 320                                        subFolderID, dirIndex);
 321
 322   if (gIsHFSPlus && (*flags == kFlatFileType)) {
 323     hfsPlusFile = (HFSPlusCatalogFile *)entry;
 324     if ((hfsPlusFile->userInfo.fdType == kHardLinkFileType) &&
 325         (hfsPlusFile->userInfo.fdCreator == kHFSPlusCreator)) {
 326       sprintf(gLinkTemp, "%s\\%s%d", HFSPLUSMETADATAFOLDER,
 327               HFS_INODE_PREFIX, hfsPlusFile->bsdInfo.special.iNodeNum);
 328       result = ResolvePathToCatalogEntry(gLinkTemp, flags, entry,
 329                                          kHFSRootFolderID, &tmpDirIndex);
 330     }
 331   }
 332
 333   return result;
 334 }
 335
 336 static long GetCatalogEntry(long *dirIndex, char **name,
 337                             long *flags, long *time)
 338 {
 339   long              extentSize, nodeSize, curNode, index, tmpTime;
 340   void              *extent;
 341   char              *nodeBuf, *testKey, *recordData;
 342   BTNodeDescriptor  *node;
 343
 344   if (gIsHFSPlus) {
 345     extent     = &gHFSPlus->catalogFile.extents;
 346     extentSize = gHFSPlus->catalogFile.logicalSize;
 347   } else {
 348     extent     = (HFSExtentDescriptor *)&gHFSMDB->drCTExtRec;
 349     extentSize = gHFSMDB->drCTFlSize;
 350   }
 351
 352   nodeSize = gBTHeaders[kBTreeCatalog]->nodeSize;
 353   nodeBuf = (char *)malloc(nodeSize);
 354   node = (BTNodeDescriptor *)nodeBuf;
 355
 356   index   = *dirIndex % nodeSize;
 357   curNode = *dirIndex / nodeSize;
 358
 359   // Read the BTree node and get the record for index.
 360   ReadExtent(extent, extentSize, kHFSCatalogFileID,
 361              curNode * nodeSize, nodeSize, nodeBuf, 1);
 362   GetBTreeRecord(index, nodeBuf, nodeSize, &testKey, &recordData);
 363
 364   // Get the kind of file.
 365   switch (*(short *)recordData) {
 366   case kHFSFolderRecord           :
 367     *flags = kDirectoryFileType;
 368     tmpTime = ((HFSCatalogFolder *)recordData)->modifyDate;
 369     break;
 370
 371   case kHFSPlusFolderRecord       :
 372     *flags = kDirectoryFileType;
 373     tmpTime = ((HFSPlusCatalogFolder *)recordData)->contentModDate;
 374     break;
 375
 376   case kHFSFileRecord             :
 377     *flags = kFlatFileType;
 378     tmpTime = ((HFSCatalogFile *)recordData)->modifyDate;
 379     break;
 380
 381   case kHFSPlusFileRecord         :
 382     *flags = kFlatFileType;
 383     tmpTime = ((HFSPlusCatalogFile *)recordData)->contentModDate;
 384     break;
 385
 386   case kHFSFileThreadRecord       :
 387   case kHFSPlusFileThreadRecord   :
 388   case kHFSFolderThreadRecord     :
 389   case kHFSPlusFolderThreadRecord :
 390     *flags = kUnknownFileType;
 391     tmpTime = 0;
 392     break;
 393   }
 394
 395   // Convert base time from 1904 to 1970.
 396   *time = tmpTime - 2082844800;
 397
 398   // Get the file name.
 399   if (gIsHFSPlus) {
 400     utf_encodestr(((HFSPlusCatalogKey *)testKey)->nodeName.unicode,
 401                   ((HFSPlusCatalogKey *)testKey)->nodeName.length,
 402                   gTempStr, 256);
 403   } else {
 404     strncpy(gTempStr,
 405             &((HFSCatalogKey *)testKey)->nodeName[1],
 406             ((HFSCatalogKey *)testKey)->nodeName[0]);
 407   }
 408   *name = gTempStr;
 409
 410   // Update dirIndex.
 411   index++;
 412   if (index == node->numRecords) {
 413     index = 0;
 414     curNode = node->fLink;
 415   }
 416   *dirIndex = curNode * nodeSize + index;
 417
 418   free(nodeBuf);
 419
 420   return 0;
 421 }
 422
 423 static long ReadCatalogEntry(char *fileName, long dirID,
 424                              void *entry, long *dirIndex)
 425 {
 426   long              length;
 427   char              key[sizeof(HFSPlusCatalogKey)];
 428   HFSCatalogKey     *hfsKey     = (HFSCatalogKey *)key;
 429   HFSPlusCatalogKey *hfsPlusKey = (HFSPlusCatalogKey *)key;
 430
 431   // Make the catalog key.
 432   if (gIsHFSPlus) {
 433     hfsPlusKey->parentID = dirID;
 434     length = strlen(fileName);
 435     if (length > 255) length = 255;
 436     utf_decodestr(fileName, hfsPlusKey->nodeName.unicode,
 437                   &(hfsPlusKey->nodeName.length), 512);
 438   } else {
 439     hfsKey->parentID = dirID;
 440     length = strlen(fileName);
 441     if (length > 31) length = 31;
 442     hfsKey->nodeName[0] = length;
 443     strncpy(hfsKey->nodeName + 1, fileName, length);
 444   }
 445
 446   return ReadBTreeEntry(kBTreeCatalog, &key, entry, dirIndex);
 447 }
 448
 449 static long ReadExtentsEntry(long fileID, long startBlock, void *entry)
 450 {
 451   char             key[sizeof(HFSPlusExtentKey)];
 452   HFSExtentKey     *hfsKey     = (HFSExtentKey *)key;
 453   HFSPlusExtentKey *hfsPlusKey = (HFSPlusExtentKey *)key;
 454
 455   // Make the extents key.
 456   if (gIsHFSPlus) {
 457     hfsPlusKey->forkType   = 0;
 458     hfsPlusKey->fileID     = fileID;
 459     hfsPlusKey->startBlock = startBlock;
 460   } else {
 461     hfsKey->forkType   = 0;
 462     hfsKey->fileID     = fileID;
 463     hfsKey->startBlock = startBlock;
 464   }
 465
 466   return ReadBTreeEntry(kBTreeExtents, &key, entry, 0);
 467 }
 468
 469 static long ReadBTreeEntry(long btree, void *key, char *entry, long *dirIndex)
 470 {
 471   long             extentSize;
 472   void             *extent;
 473   short            extentFile;
 474   char             *nodeBuf;
 475   BTNodeDescriptor *node;
 476   long             nodeSize, result, entrySize;
 477   long             curNode, index, lowerBound, upperBound;
 478   char             *testKey, *recordData;
 479
 480   // Figure out which tree is being looked at.
 481   if (btree == kBTreeCatalog) {
 482     if (gIsHFSPlus) {
 483       extent     = &gHFSPlus->catalogFile.extents;
 484       extentSize = gHFSPlus->catalogFile.logicalSize;
 485     } else {
 486       extent     = (HFSExtentDescriptor *)&gHFSMDB->drCTExtRec;
 487       extentSize = gHFSMDB->drCTFlSize;
 488     }
 489     extentFile = kHFSCatalogFileID;
 490   } else {
 491     if (gIsHFSPlus) {
 492       extent     = &gHFSPlus->extentsFile.extents;
 493       extentSize = gHFSPlus->extentsFile.logicalSize;
 494     } else {
 495       extent     = (HFSExtentDescriptor *)&gHFSMDB->drXTExtRec;
 496       extentSize = gHFSMDB->drXTFlSize;
 497     }
 498     extentFile = kHFSExtentsFileID;
 499   }
 500
 501   // Read the BTree Header if needed.
 502   if (gBTHeaders[btree] == 0) {
 503     ReadExtent(extent, extentSize, extentFile, 0, 256,
 504                gBTreeHeaderBuffer + btree * 256, 0);
 505     gBTHeaders[btree] = (BTHeaderRec *)(gBTreeHeaderBuffer + btree * 256 +
 506                                        sizeof(BTNodeDescriptor));
 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 (GetNodeType(node) == 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       result = FastUnicodeCompare(&searchKey->nodeName.unicode[0],
 758                                   searchKey->nodeName.length,
 759                                   &trialKey->nodeName.unicode[0],
 760                                   trialKey->nodeName.length);
 761   }
 762
 763   return result;
 764 }
 765
 766 static long CompareHFSExtentsKeys(void *key, void *testKey)
 767 {
 768   HFSExtentKey *searchKey, *trialKey;
 769   long         result;
 770
 771   searchKey = key;
 772   trialKey  = testKey;
 773
 774   // assume searchKey < trialKey
 775   result = -1;
 776
 777   if (searchKey->fileID == trialKey->fileID) {
 778     // FileNum's are equal; compare fork types
 779     if (searchKey->forkType == trialKey->forkType) {
 780       // Fork types are equal; compare allocation block number
 781       if (searchKey->startBlock == trialKey->startBlock) {
 782         // Everything is equal
 783         result = 0;
 784       } else {
 785         // Allocation block numbers differ; determine sign
 786         if (searchKey->startBlock > trialKey->startBlock) result = 1;
 787       }
 788     } else {
 789       // Fork types differ; determine sign
 790       if (searchKey->forkType > trialKey->forkType) result = 1;
 791     }
 792   } else {
 793     // FileNums differ; determine sign
 794     if (searchKey->fileID > trialKey->fileID) result = 1;
 795   }
 796
 797   return result;
 798 }
 799
 800 static long CompareHFSPlusExtentsKeys(void *key, void *testKey)
 801 {
 802   HFSPlusExtentKey *searchKey, *trialKey;
 803   long             result;
 804
 805   searchKey = key;
 806   trialKey  = testKey;
 807
 808   // assume searchKey < trialKey
 809   result = -1;
 810
 811   if (searchKey->fileID == trialKey->fileID) {
 812     // FileNum's are equal; compare fork types
 813     if (searchKey->forkType == trialKey->forkType) {
 814       // Fork types are equal; compare allocation block number
 815       if (searchKey->startBlock == trialKey->startBlock) {
 816         // Everything is equal
 817         result = 0;
 818       } else {
 819         // Allocation block numbers differ; determine sign
 820         if (searchKey->startBlock > trialKey->startBlock) result = 1;
 821       }
 822     } else {
 823       // Fork types differ; determine sign
 824       if (searchKey->forkType > trialKey->forkType) result = 1;
 825     }
 826   } else {
 827     // FileNums differ; determine sign
 828     if (searchKey->fileID > trialKey->fileID) result = 1;
 829   }
 830
 831   return result;
 832 }