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