i386/libsaio/hfs.c

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