qemu/roms/openbios/fs/grubfs/fsys_ntfs.c

   1 /* vim: set sw=4 :*/
   2 /*
   3  *  GRUB  --  GRand Unified Bootloader
   4  *  Copyright (C) 1999  Free Software Foundation, Inc.
   5  *
   6  *  This program is free software; you can redistribute it and/or modify
   7  *  it under the terms of the GNU General Public License as published by
   8  *  the Free Software Foundation; either version 2 of the License, or
   9  *  (at your option) any later version.
  10  *
  11  *  This program is distributed in the hope that it will be useful,
  12  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14  *  GNU General Public License for more details.
  15  *
  16  *  You should have received a copy of the GNU General Public License
  17  *  along with this program; if not, write to the Free Software
  18  *  Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston,
  19  *  MA 02110-1301, USA.
  20  */
  21
  22 /*
  23  * Samuel Leo <samuel@_.remove.me._szonline.net>
  24  * Limitations:
  25  * 1. Only 32 bit size support
  26  * 2. don't support >1k MFT record size, >16k INDEX record size
  27  * 3. don't support recursive at_attribute_list
  28  * 4. don't support compressed attribute other than Datastream
  29  * 5. all MFT's at_attribute_list must resident at first run list
  30  * 6. don't support journaling
  31  * 7. don't support EFS encryption
  32  * 8. don't support mount point and junction
  33  */
  34 #ifdef FSYS_NTFS
  35
  36 //#define DEBUG_NTFS 1
  37
  38 /*
  39 #define NO_ATTRIBUTE_LIST 1
  40    totally disable at_attribute_list support,
  41    if no compressed/fragment file and MFT,
  42    not recommended
  43 #define NO_NON_RESIDENT_ATTRIBUTE_LIST 1
  44    disable non-resident at_attribute_list support,
  45    if no huge compressed/fragment file and MFT
  46 #define NO_NTFS_DECOMPRESSION 1
  47    disable ntfs compressed file support
  48 #define NO_ALTERNATE_DATASTREAM 1
  49    disable ntfs alternate datastream support
  50 */
  51
  52 #include "shared.h"
  53 #include "filesys.h"
  54
  55 #ifdef STAGE1_5
  56 /* safe turn off non-resident attribute list if MFT fragments < 4000 */
  57 //#define NO_NON_RESIDENT_ATTRIBUTE_LIST 1
  58 #define NO_NTFS_DECOMPRESSION 1
  59 #endif
  60
  61 #define MAX_MFT_RECORD_SIZE 1024
  62 #define MAX_INDEX_RECORD_SIZE 16384
  63 #define MAX_INDEX_BITMAP_SIZE 4096
  64 #define DECOMP_DEST_BUFFER_SIZE 16384
  65 #define DECOMP_SOURCE_BUFFER_SIZE (8192+2)
  66 #define MAX_DIR_DEPTH 64
  67
  68 /* sizes are always in bytes, BLOCK values are always in DEV_BSIZE (sectors) */
  69 #define DEV_BSIZE 512
  70
  71 /* include/linux/fs.h */
  72 #define BLOCK_SIZE      512
  73
  74 #define WHICH_SUPER 1
  75 #define SBLOCK (WHICH_SUPER * BLOCK_SIZE / DEV_BSIZE)   /* = 2 */
  76
  77 /* include/asm-i386/type.h */
  78 typedef __signed__ char __s8;
  79 typedef unsigned char __u8;
  80 typedef __signed__ short __s16;
  81 typedef unsigned short __u16;
  82 typedef __signed__ int __s32;
  83 typedef unsigned int __u32;
  84 typedef __signed__ long long __s64;
  85 typedef unsigned long long __u64;
  86
  87 #define FILE_MFT      0
  88 #define FILE_MFTMIRR  1
  89 #define FILE_LOGFILE  2
  90 #define FILE_VOLUME   3
  91 #define FILE_ATTRDEF  4
  92 #define FILE_ROOT     5
  93 #define FILE_BITMAP   6
  94 #define FILE_BOOT     7
  95 #define FILE_BADCLUS  8
  96 #define FILE_QUOTA    9
  97 #define FILE_UPCASE  10
  98
  99 #define at_standard_information 0x10
 100 #define at_attribute_list       0x20
 101 #define at_filename             0x30
 102 #define at_security_descriptor  0x50
 103 #define at_data                 0x80
 104 #define at_index_root           0x90
 105 #define at_index_allocation     0xa0
 106 #define at_bitmap               0xb0
 107 #define at_symlink              0xc0
 108
 109 #define NONAME  ""
 110 #define ATTR_NORMAL     0
 111 #define ATTR_COMPRESSED 1
 112 #define ATTR_RESIDENT   2
 113 #define ATTR_ENCRYPTED  16384
 114 #define ATTR_SPARSE     32768
 115
 116 typedef struct run_list {
 117         char *start;
 118         char *ptr;
 119         int svcn;
 120         int evcn;
 121         int vcn;
 122         int cnum0;
 123         int cnum;
 124         int clen;
 125 } RUNL;
 126
 127 typedef struct ntfs_mft_record {
 128         char mft[MAX_MFT_RECORD_SIZE];
 129         char mft2[MAX_MFT_RECORD_SIZE];
 130         int attr_type;
 131         char *attr_name;
 132         int attr_flag;
 133         int attr_size;
 134         char *attr;
 135         int attr_len;
 136         RUNL runl;
 137         char *attr_list;
 138         int attr_list_len;
 139         int attr_list_size;
 140         int attr_list_off;
 141         int attr_inited;
 142         char attr_list_buf[2*BLOCK_SIZE];
 143         RUNL attr_list_runl;
 144 } MFTR;
 145
 146
 147 #define index_data      ((char *)FSYS_BUF)
 148 #define bitmap_data     ((__u8 *)(FSYS_BUF+MAX_INDEX_RECORD_SIZE))
 149 #define dcdbuf  ((__u8 *)index_data)
 150 #define dcsbuf  (bitmap_data)
 151 #define dcend   (dcsbuf+DECOMP_SOURCE_BUFFER_SIZE)
 152 #define fnbuf ((char *)(bitmap_data+MAX_INDEX_BITMAP_SIZE))
 153 #define mmft    ((MFTR *)dcend)
 154 #define cmft    ((MFTR *)(dcend+sizeof(MFTR)))
 155 #define mft_run ((RUNL *)(dcend+2*sizeof(MFTR)))
 156 #define path_ino ((int *)(dcend+2*sizeof(MFTR)+sizeof(RUNL)))
 157 #define cluster16 (path_ino+MAX_DIR_DEPTH)
 158 #define index16 cluster16[16]
 159 #define blocksize cluster16[17]
 160 #define clustersize cluster16[18]
 161 #define mft_record_size cluster16[19]
 162 #define index_record_size cluster16[20]
 163 #define dcvcn cluster16[21]
 164 #define dcoff cluster16[22]
 165 #define dclen cluster16[23]
 166 #define dcrem cluster16[24]
 167 #define dcslen cluster16[25]
 168 #define dcsptr ((__u8 *)cluster16[26])
 169 #define is_ads_completion cluster16[27]
 170
 171 static int read_mft_record(int mftno, char *mft, int self);
 172 static int read_attribute(MFTR *mftr, int offset, char *buf, int len, RUNL *from_rl);
 173 static int get_next_run(RUNL *runl);
 174
 175 static inline int
 176 nsubstring (char *s1, char *s2)
 177 {
 178     while (tolower(*s1) == tolower(*s2))
 179     {
 180         /* The strings match exactly. */
 181         if (! *(s1++))
 182             return 0;
 183         s2 ++;
 184     }
 185
 186     /* S1 is a substring of S2. */
 187     if (*s1 == 0)
 188         return -1;
 189
 190     /* S1 isn't a substring. */
 191     return 1;
 192 }
 193
 194 static int fixup_record(char *record, char *magic, int size)
 195 {
 196     int start, count, offset;
 197     __u16 fixup;
 198
 199     if(*(int *)record != *(int *)magic)
 200         return 0;
 201     start=*(__u16 *)(record+4);
 202     count=*(__u16 *)(record+6);
 203     count--;
 204     if(size && blocksize*count != size)
 205         return 0;
 206     fixup = *(__u16 *)(record+start);
 207     start+=2;
 208     offset=blocksize-2;
 209     while(count--){
 210         if(*(__u16 *)(record+offset)!=fixup)
 211             return 0;
 212         *(__u16 *)(record+offset) = *(__u16 *)(record+start);
 213         start+=2;
 214         offset+=blocksize;
 215     }
 216     return 1;
 217 }
 218
 219 static void rewind_run_list( RUNL *runl) {
 220     runl->vcn = runl->svcn;
 221     runl->ptr = runl->start;
 222     runl->cnum0 = 0;
 223     runl->cnum = 0;
 224     runl->clen = 0;
 225 }
 226
 227 static int get_next_run(RUNL *runl){
 228     int t, n, v;
 229
 230 #ifdef DEBUG_NTFS
 231     printf("get_next_run: s=%d e=%d c=%d start=%x ptr=%x\n",
 232            runl->svcn, runl->evcn, runl->vcn, runl->start, runl->ptr);
 233 #endif
 234
 235     runl->vcn += runl->clen;
 236     if(runl->vcn > runl->evcn) {
 237         return 0;
 238     }
 239
 240     t = *(runl->ptr)++;
 241     n = t&0xf;
 242     runl->clen = 0; v = 1;
 243     while(n--) {
 244         runl->clen += v * *((__u8 *)runl->ptr)++;
 245         v <<= 8;
 246     }
 247     n = (t>>4)&0xf;
 248     if(n==0)
 249         runl->cnum = 0;
 250     else {
 251         int c = 0;
 252         v = 1;
 253         while(n--) {
 254             c += v * *((__u8 *)runl->ptr)++;
 255             v <<= 8;
 256         }
 257         if(c & (v>>1)) c -= v;
 258         runl->cnum0 += c;
 259         runl->cnum = runl->cnum0;
 260     }
 261 #ifdef DEBUG_NTFS
 262     printf("got_next_run: t=%x cluster %x len %x vcn=%x ecn=%x\n",
 263         t, runl->cnum, runl->clen, runl->vcn, runl->evcn);
 264 #endif
 265     return 1;
 266 }
 267
 268 #ifndef NO_ATTRIBUTE_LIST
 269 static void init_run_list(char *attr, int len, RUNL *runl, __u32 *initp) {
 270     int allocated;
 271
 272     runl->svcn = *(__u32 *)(attr+0x10); /* only support 32 bit */
 273     runl->evcn = *(__u32 *)(attr+0x18); /* only support 32 bit */
 274     runl->start = attr + *(__u16 *)(attr+0x20);
 275     allocated = *(__u32 *)(attr+0x28);
 276     if(initp) *initp = *(__u32 *)(attr+0x38);
 277     if(!runl->evcn) runl->evcn = (allocated - 1) / clustersize;
 278 #ifdef DEBUG_NTFS
 279     printf("size %d allocated=%d inited=%d cegin=%x csize=%d vcn=%d-%d\n",
 280             /*attr_size*/ *(__u32 *)(attr+0x30),
 281             /*allocated*/ *(__u32 *)(attr+0x28),
 282             /*attr_inited*/ *(__u32 *)(attr+0x38),
 283             /*cengin*/ *(__u16 *)(attr+0x22),
 284             /*csize*/ *(__u16 *)(attr+0x40),
 285             runl->svcn, runl->evcn);
 286 #endif
 287     rewind_run_list(runl);
 288 }
 289 #endif
 290
 291
 292 static int find_attribute(char *mft, int type, char *name, char **attr, int *size, int *len, int *flag) {
 293     int t, l, r, n, i, namelen;
 294     unsigned short *attr_name;
 295
 296     n = strlen(name);
 297     r = mft_record_size - *(__u16 *)(mft+0x14);
 298     mft += *(__u16 *)(mft+0x14);
 299     while( (t = *(__s32 *)mft) != -1 ) {
 300         l = *(__u32 *)(mft+4);
 301         if(l>r) break;
 302 #ifdef DEBUG_NTFS
 303         printf("type = %x len = %d namelen=%d resident=%d compresed=%d attrno=%d\n",
 304                 t, l,
 305                 /*namelen*/ *(mft+9),
 306                 //name = (__u16 *)(mft + *(__u16 *)(mft+10)),
 307                 /*resident */ (*(mft+8) == 0),
 308                 /*compressed*/ *(__u16 *)(mft+12),
 309                 /*attrno*/ *(__u16 *)(mft+14));
 310 #endif
 311         namelen = *(mft+9);
 312         if(t == type) {
 313 #ifndef STAGE1_5
 314 #ifndef NO_ALTERNATE_DATASTREAM
 315             if(is_ads_completion && type == at_data) {
 316                 if(namelen && namelen >= n &&
 317                    (!*(mft+8)/*resident*/ || !*(__u32 *)(attr+0x10)/*svcn==0*/))
 318                 {
 319                     for(i=0, attr_name=(__u16 *)(mft + *(__u16 *)(mft+10)); i < n; i++)
 320                         if(tolower(name[i]) != tolower(attr_name[i]))
 321                             break;
 322                     if(i >= n) {
 323                         for(; i < namelen; i++)
 324                             name[i] = attr_name[i];
 325                         name[i] = '\0';
 326                         if(print_possibilities > 0)
 327                             print_possibilities = -print_possibilities;
 328                         print_a_completion(fnbuf);
 329                         name[n] = '\0';
 330                     }
 331                 }
 332             } else
 333 #endif
 334 #endif
 335                 if(namelen == n) {
 336
 337                 for(i=0, attr_name=(__u16 *)(mft + *(__u16 *)(mft+10)); i<n; i++)
 338                     if(tolower(name[i]) != tolower(attr_name[i]))
 339                         break;
 340                 if(i>=n) {
 341                     if(flag) *flag = *(__u16 *)(mft+12);
 342                     if(*(mft+8) == 0) {
 343                         if(flag) *flag |= ATTR_RESIDENT;
 344 #ifdef DEBUG_NTFS
 345                         printf("resident data at %x size %x indexed=%d\n",
 346                                /*data*/ *(__u16 *)(mft+0x14),
 347                                /*attr_size*/ *(__u16 *)(mft+0x10),
 348                                /*indexed*/ *(__u16 *)(mft+0x16));
 349 #endif
 350                         if(attr) *attr = mft + *(__u16 *)(mft+0x14);
 351                         if(size) *size = *(__u16 *)(mft+0x10);
 352                         if(len) *len = *(__u16 *)(mft+0x10);
 353                     } else {
 354                         if(attr) *attr = mft;
 355                         if(size) *size = *(__u32 *)(mft+0x30);
 356                         if(len) *len = l;
 357                     }
 358                     return 1;
 359                 }
 360             }
 361         }
 362         mft += l;
 363         r -= l;
 364     }
 365     return 0;
 366 }
 367
 368 #ifndef NO_ATTRIBUTE_LIST
 369 static __u32 get_next_attribute_list(MFTR *mftr, int *size) {
 370     int l, t, mftno;
 371 #ifdef DEBUG_NTFS
 372     printf("get_next_attribute_list: type=%x\n",mftr->attr_type);
 373 #endif
 374 again:
 375     while(mftr->attr_list_len>0x14) {
 376         t = *(__u32 *)(mftr->attr_list + 0);
 377         l = *(__u16 *)(mftr->attr_list + 4);
 378 #ifdef DEBUG_NTFS
 379         printf("attr_list type=%x len=%x remain=%x\n", t, l, mftr->attr_list_len);
 380 #endif
 381         if(l==0 || l>mftr->attr_list_len) return 0;
 382         mftno = *(__u32 *)(mftr->attr_list + 0x10);
 383         mftr->attr_list_len -= l;
 384         mftr->attr_list += l;
 385         if(t==mftr->attr_type)
 386         {
 387 #ifdef DEBUG_NTFS
 388         printf("attr_list mftno=%x\n", mftno);
 389 #endif
 390             if(read_mft_record(mftno, mftr->mft2, (mftr==mmft))==0)
 391                 break;
 392             if(find_attribute(mftr->mft2, mftr->attr_type, mftr->attr_name,
 393                         &mftr->attr, size, &mftr->attr_len, &mftr->attr_flag))
 394                 return 1;
 395         }
 396     }
 397 #ifndef NO_NON_RESIDENT_ATTRIBUTE_LIST
 398     if(mftr->attr_list_off < mftr->attr_list_size) {
 399         int len = mftr->attr_list_size - mftr->attr_list_off;
 400         if(len > BLOCK_SIZE) len = BLOCK_SIZE;
 401
 402         if(mftr->attr_list_len)
 403             memmove(mftr->attr_list_buf, mftr->attr_list, mftr->attr_list_len);
 404         mftr->attr_list = mftr->attr_list_buf;
 405
 406         if(read_attribute( NULL, mftr->attr_list_off,
 407                         mftr->attr_list_buf + mftr->attr_list_len,
 408                         len, &mftr->attr_list_runl) != len)
 409         {
 410 #ifdef DEBUG_NTFS
 411             printf("CORRUPT NON-RESIDENT ATTRIBUTE_LIST\n");
 412 #endif
 413             /* corrupt */
 414             errnum = ERR_FSYS_CORRUPT;
 415             mftr->attr_list_size = 0;
 416             mftr->attr_len = 0;
 417             mftr->attr_list = NULL;
 418             return 0;
 419         }
 420
 421         mftr->attr_list_len += len;
 422         mftr->attr_list_off += len;
 423         goto again;
 424     }
 425 #endif
 426     mftr->attr_list = NULL;
 427     return 0;
 428 }
 429 #endif
 430
 431 static int search_attribute( MFTR *mftr, int type, char *name)
 432 {
 433 #ifdef DEBUG_NTFS
 434     printf("searching attribute %x <%s>\n", type, name);
 435 #endif
 436
 437     mftr->attr_type = type;
 438     mftr->attr_name = name;
 439     mftr->attr_list = NULL;
 440     mftr->attr_list_len = 0;
 441     mftr->attr_list_size = 0;
 442     mftr->attr_list_off = 0;
 443     dcrem = dclen = 0;
 444
 445 #ifndef NO_ATTRIBUTE_LIST
 446     if(find_attribute(mftr->mft, at_attribute_list, NONAME,
 447                       &mftr->attr_list, &mftr->attr_list_size,
 448                       &mftr->attr_list_len, &mftr->attr_list_off)) {
 449         if(mftr->attr_list_off&ATTR_RESIDENT) {
 450             /* resident at_attribute_list */
 451             mftr->attr_list_size = 0;
 452 #ifdef DEBUG_NTFS
 453             printf("resident attribute_list len=%x\n", mftr->attr_list_len);
 454 #endif
 455         } else {
 456 #ifdef DEBUG_NTFS
 457             printf("non-resident attribute_list len=%x size=%x\n",
 458                    mftr->attr_list_len, mftr->attr_list_size);
 459 #endif
 460 #ifndef NO_NON_RESIDENT_ATTRIBUTE_LIST
 461             init_run_list(mftr->attr_list, mftr->attr_list_len, &mftr->attr_list_runl, NULL);
 462             if(get_next_run(&mftr->attr_list_runl)==0 ||
 463                mftr->attr_list_runl.cnum==0)
 464                 mftr->attr_list_size = 0;
 465 #endif
 466             mftr->attr_list = NULL;
 467             mftr->attr_list_len = 0;
 468         }
 469     }
 470 #endif
 471
 472     if(find_attribute(mftr->mft, type, name,
 473                       &mftr->attr, &mftr->attr_size, &mftr->attr_len,
 474                       &mftr->attr_flag)
 475 #ifndef NO_ATTRIBUTE_LIST
 476        || get_next_attribute_list(mftr, &mftr->attr_size)
 477 #endif
 478        )
 479     {
 480 #ifndef NO_ATTRIBUTE_LIST
 481         if(!(mftr->attr_flag&ATTR_RESIDENT)){
 482             init_run_list(mftr->attr, mftr->attr_len, &mftr->runl, &mftr->attr_inited);
 483             if(mftr->attr_inited > mftr->attr_size)
 484                 mftr->attr_inited = mftr->attr_size;
 485             if(get_next_run(&mftr->runl)==0) {
 486                 mftr->attr_flag |= ATTR_RESIDENT;
 487                 mftr->attr_len = 0;
 488             }
 489         } else
 490             mftr->attr_inited = mftr->attr_size;
 491 #endif
 492
 493         return 1;
 494     }
 495
 496     mftr->attr_type = 0;
 497     return 0;
 498 }
 499
 500 static int get_run( RUNL *rl, int vcn, int *clp, int *lenp) {
 501     if(rl->evcn < vcn)
 502         return 0;
 503
 504     if(rl->vcn > vcn) {
 505         rewind_run_list(rl);
 506         get_next_run(rl);
 507     }
 508
 509     while(rl->vcn+rl->clen <= vcn)
 510     {
 511         if(get_next_run(rl)==0)
 512             return 0;
 513     }
 514
 515     if(clp) *clp = rl->cnum == 0 ? 0 : rl->cnum + vcn - rl->vcn;
 516     if(lenp) *lenp = rl->clen - vcn + rl->vcn;
 517     return 1;
 518 }
 519
 520 static int search_run(MFTR *mftr, int vcn) {
 521
 522     if( mftr->attr==NULL && !search_attribute(mftr, mftr->attr_type, mftr->attr_name))
 523         return 0;
 524
 525     if(mftr->runl.svcn > vcn)
 526         search_attribute(mftr, mftr->attr_type, mftr->attr_name);
 527
 528 #ifdef NO_ATTRIBUTE_LIST
 529     if(mftr->runl.evcn < vcn)
 530         return 0;
 531 #else
 532     while(mftr->runl.evcn < vcn) {
 533         if(get_next_attribute_list(mftr, NULL)==0) {
 534             mftr->attr = NULL;
 535             return 0;
 536         }
 537         init_run_list(mftr->attr, mftr->attr_len, &mftr->runl, NULL);
 538         if(get_next_run(&mftr->runl)==0) {
 539             mftr->attr = NULL;
 540             return 0;
 541         }
 542     }
 543 #endif
 544
 545     return 1;
 546 }
 547
 548 static int read_attribute(MFTR *mftr, int offset, char *buf, int len, RUNL *from_rl) {
 549     int vcn;
 550     int cnum, clen;
 551     int done = 0;
 552     int n;
 553     RUNL *rl;
 554
 555     if(!from_rl && (mftr->attr_flag & ATTR_RESIDENT)) {
 556         /* resident attribute */
 557         if(offset > mftr->attr_len)
 558             return 0;
 559         if(offset+len > mftr->attr_len)
 560             len = mftr->attr_len - offset;
 561         memmove( buf, mftr->attr + offset, len);
 562         return len;
 563     }
 564
 565     vcn = offset / clustersize;
 566     offset %= clustersize;
 567
 568     while(len>0) {
 569         if(from_rl)
 570             rl = from_rl;
 571         else if(search_run(mftr, vcn) == 0)
 572             break;
 573         else
 574             rl = &mftr->runl;
 575         if(get_run(rl, vcn, &cnum, &clen) == 0)
 576             break;
 577         if(cnum==0 && from_rl)
 578             break;
 579         n = clen * clustersize - offset;
 580         if(n > len) n = len;
 581         if(cnum==0) {
 582             memset( buf, 0, n);
 583         } else if(!devread(cnum*(clustersize>>9)+(offset>>9), offset&0x1ff, n, buf))
 584             break;
 585
 586         buf += n;
 587         vcn += (offset+n)/clustersize;
 588         done += n;
 589         offset = 0;
 590         len -= n;
 591     }
 592     return done;
 593 }
 594
 595 static int read_mft_record(int mftno, char *mft, int self){
 596 #ifdef DEBUG_NTFS
 597     printf("Reading MFT record: mftno=%d\n", mftno);
 598 #endif
 599     if( read_attribute( mmft, mftno * mft_record_size,
 600             mft, mft_record_size, self?mft_run:NULL) != mft_record_size)
 601         return 0;
 602     if(!fixup_record( mft, "FILE", mft_record_size))
 603         return 0;
 604     return 1;
 605 }
 606
 607 #ifndef NO_NTFS_DECOMPRESSION
 608 static int get_16_cluster(MFTR *mftr, int vcn) {
 609     int n = 0, cnum, clen;
 610     while(n < 16 && search_run(mftr, vcn) && get_run(&mftr->runl, vcn, &cnum, &clen) && cnum) {
 611         if(clen > 16 - n)
 612             clen = 16 - n;
 613         vcn += clen;
 614         while(clen--)
 615             cluster16[n++] = cnum++;
 616     }
 617     cluster16[n] = 0;
 618     return n;
 619 }
 620
 621 static inline int compressed_block_size( unsigned char *src ) {
 622     return 3 + (*(__u16 *)src & 0xfff);
 623 }
 624
 625 static int decompress_block(unsigned char *dest, unsigned char *src) {
 626     int head;
 627     int copied=0;
 628     unsigned char *last;
 629     int bits;
 630     int tag=0;
 631
 632     /* high bit indicates that compression was performed */
 633     if(!(*(__u16 *)src & 0x8000)) {
 634         memmove(dest,src+2,0x1000);
 635         return 0x1000;
 636     }
 637
 638     if((head = *(__u16 *)src & 0xFFF)==0)
 639         /* block is not used */
 640         return 0;
 641
 642     src += 2;
 643     last = src+head;
 644     bits = 0;
 645
 646     while(src<=last)
 647     {
 648         if(copied>4096)
 649         {
 650 #ifdef DEBUG_NTFS
 651             printf("decompress error 1\n");
 652 #endif
 653             errnum = ERR_FSYS_CORRUPT;
 654             return 0;
 655         }
 656         if(!bits){
 657             tag=*(__u8 *)src;
 658             bits=8;
 659             src++;
 660             if(src>last)
 661                 break;
 662         }
 663         if(tag & 1){
 664             int i,len,delta,code,lmask,dshift;
 665             code = *(__u16 *)src;
 666             src+=2;
 667             if(!copied)
 668             {
 669 #ifdef DEBUG_NTFS
 670                 printf("decompress error 2\n");
 671 #endif
 672                 errnum = ERR_FSYS_CORRUPT;
 673                 return 0;
 674             }
 675             for(i=copied-1,lmask=0xFFF,dshift=12;i>=0x10;i>>=1)
 676             {
 677                 lmask >>= 1;
 678                 dshift--;
 679             }
 680             delta = code >> dshift;
 681             len = (code & lmask) + 3;
 682             for(i=0; i<len; i++)
 683             {
 684                 dest[copied]=dest[copied-delta-1];
 685                 copied++;
 686             }
 687         } else
 688             dest[copied++]=*(__u8 *)src++;
 689         tag>>=1;
 690         bits--;
 691     }
 692
 693     return copied;
 694 }
 695 #endif
 696
 697 int ntfs_read(char *buf, int len){
 698     int ret;
 699 #ifdef STAGE1_5
 700 /* stage2 can't be resident/compressed/encrypted files,
 701  * but does sparse flag, cause stage2 never sparsed
 702  */
 703     if((cmft->attr_flag&~ATTR_SPARSE) != ATTR_NORMAL)
 704         return 0;
 705     disk_read_func = disk_read_hook;
 706     ret = read_attribute(cmft, filepos, buf, len, 0);
 707     disk_read_func = NULL;
 708     filepos += ret;
 709 #else
 710
 711 #ifndef NO_NTFS_DECOMPRESSION
 712     int off;
 713     int vcn;
 714     int size;
 715     int len0;
 716 #endif
 717
 718     if(len<=0 || filepos >= cmft->attr_size || (cmft->attr_flag&ATTR_ENCRYPTED))
 719         return 0;
 720
 721     if(filepos+len > cmft->attr_size)
 722         len = cmft->attr_size - filepos;
 723     if(filepos >= cmft->attr_inited) {
 724 #ifdef DEBUG_NTFS
 725 printf("reading uninitialized data 1\n");
 726 #endif
 727         memset(buf, 0, len);
 728         return len;
 729     } else if(filepos+len > cmft->attr_inited) {
 730         len0 = len;
 731         len = cmft->attr_inited - filepos;
 732         len0 -= len;
 733     } else
 734         len0 = 0;
 735 #ifdef DEBUG_NTFS
 736 printf("read filepos=%x filemax=%x inited=%x len=%x len0=%x\n",filepos,filemax,cmft->attr_inited,len,len0);
 737 #endif
 738
 739     if((cmft->attr_flag&(ATTR_COMPRESSED|ATTR_RESIDENT)) != ATTR_COMPRESSED) {
 740         if(cmft->attr_flag==ATTR_NORMAL)
 741             disk_read_func = disk_read_hook;
 742         ret = read_attribute(cmft, filepos, buf, len, 0);
 743         if(cmft->attr_flag==ATTR_NORMAL)
 744             disk_read_func = NULL;
 745         filepos += ret;
 746         if(ret==len && len0) {
 747                 memset(buf+len, 0, len0);
 748                 filepos += len0;
 749                 ret += len0;
 750         }
 751         return ret;
 752     }
 753
 754     ret = 0;
 755
 756 #ifndef NO_NTFS_DECOMPRESSION
 757     /* NTFS don't support compression if cluster size > 4k */
 758     if(clustersize > 4096) {
 759         errnum = ERR_FSYS_CORRUPT;
 760         return 0;
 761     }
 762
 763     while(len > 0){
 764 #ifdef DEBUG_NTFS
 765 printf("Reading filepos=%x len=%x\n", filepos, len);
 766 #endif
 767         if(filepos >= dcoff && filepos < (dcoff+dclen)) {
 768 #ifdef DEBUG_NTFS
 769 printf("decompress cache %x+%x\n", dcoff, dclen);
 770 #endif
 771             size = dcoff + dclen - filepos;
 772             if(size > len) size = len;
 773             memmove( buf, dcdbuf + filepos - dcoff, size);
 774             filepos += size;
 775             len -= size;
 776             ret += size;
 777             buf += size;
 778             if(len==0) {
 779                 if(len0) {
 780 #ifdef DEBUG_NTFS
 781 printf("reading uninitialized data 2\n");
 782 #endif
 783                     memset(buf, 0, len0);
 784                     filepos += len0;
 785                     ret += len0;
 786                 }
 787                 return ret;
 788             }
 789         }
 790
 791         vcn = filepos / clustersize / 16;
 792         vcn *= 16;
 793         off = filepos % (16 * clustersize);
 794         if( dcvcn != vcn || filepos < dcoff)
 795             dcrem = 0;
 796
 797 #ifdef DEBUG_NTFS
 798 printf("vcn %x off %x dcrem %x\n", vcn, off, dcrem);
 799 #endif
 800         if(dcrem) {
 801             int head;
 802
 803             /* reading source */
 804             if(dcslen < 2 || compressed_block_size(dcsptr) > dcslen) {
 805                 if(cluster16[index16]==0) {
 806                     errnum = ERR_FSYS_CORRUPT;
 807                     return ret;
 808                 }
 809                 if(dcslen)
 810                     memmove(dcsbuf, dcsptr, dcslen);
 811                 dcsptr = dcsbuf;
 812                 while((dcslen+clustersize) < DECOMP_SOURCE_BUFFER_SIZE) {
 813                     if(cluster16[index16]==0)
 814                         break;
 815 #ifdef DEBUG_NTFS
 816 printf("reading dcslen=%x cluster %x\n", dcslen, cluster16[index16]);
 817 #endif
 818                     if(!devread(cluster16[index16]*(clustersize>>9), 0, clustersize, dcsbuf+dcslen))
 819                         return ret;
 820                     dcslen += clustersize;
 821                     index16++;
 822                 }
 823             }
 824             /* flush destination */
 825             dcoff += dclen;
 826             dclen = 0;
 827
 828             while(dcrem && dclen < DECOMP_DEST_BUFFER_SIZE &&
 829                   dcslen >= 2 && (head=compressed_block_size(dcsptr)) <= dcslen) {
 830                 size = decompress_block(dcdbuf+dclen, dcsptr);
 831                 if(dcrem>=0x1000 && size!=0x1000) {
 832                     errnum = ERR_FSYS_CORRUPT;
 833                     return ret;
 834                 }
 835                 dcrem -= size;
 836                 dclen += size;
 837                 dcsptr += head;
 838                 dcslen -= head;
 839             }
 840             continue;
 841         }
 842         dclen = dcrem = 0;
 843 #ifdef DEBUG_NTFS
 844 printf("get next 16 clusters\n");
 845 #endif
 846         switch(get_16_cluster(cmft, vcn)) {
 847         case 0:
 848 #ifdef DEBUG_NTFS
 849 printf("sparse\n");
 850 #endif
 851             /* sparse */
 852             size = 16 * clustersize - off;
 853             if( len < size )
 854                 size = len;
 855 #ifndef STAGE1_5
 856             memset( buf, 0, size);
 857 #endif
 858             filepos += size;
 859             len -= size;
 860             ret += size;
 861             buf += size;
 862             break;
 863
 864         case 16:
 865 #ifdef DEBUG_NTFS
 866 printf("uncompressed\n");
 867 #endif
 868             /* uncompressed */
 869             index16 = off / clustersize;
 870             off %= clustersize;
 871             while(index16 < 16) {
 872                 size = clustersize - off;
 873                 if( len < size )
 874                     size = len;
 875                 if(!devread(cluster16[index16]*(clustersize>>9)+(off>>9), off&0x1ff, size, buf))
 876                     return ret;
 877                 filepos += size;
 878                 len -= size;
 879                 ret += size;
 880                 if(len==0)
 881                     return ret;
 882                 off = 0;
 883                 buf += size;
 884                 index16++;
 885             }
 886             break;
 887
 888         default:
 889 #ifdef DEBUG_NTFS
 890 printf("compressed\n");
 891 #endif
 892             index16 = 0;
 893             dcvcn = vcn;
 894             dcoff = vcn * clustersize;
 895             dcrem = cmft->attr_inited - dcoff;
 896             if(dcrem > 16 * clustersize)
 897                 dcrem = 16 * clustersize;
 898             dcsptr = dcsbuf;
 899             dcslen = 0;
 900         }
 901     }
 902     if(len0) {
 903 #ifdef DEBUG_NTFS
 904 printf("reading uninitialized data 3\n");
 905 #endif
 906         memset(buf, 0, len0);
 907         filepos += len0;
 908         ret += len0;
 909     }
 910 #else
 911     errnum = FSYS_CORRUPT;
 912 #endif /*NO_NTFS_DECOMPRESSION*/
 913 #endif /*STAGE1_5*/
 914     return ret;
 915 }
 916
 917 int ntfs_mount (void)
 918 {
 919     char *sb = (char *)FSYS_BUF;
 920     int mft_record;
 921     int spc;
 922
 923   if (((current_drive & 0x80) || (current_slice != 0))
 924        && (current_slice != /*PC_SLICE_TYPE_NTFS*/7)
 925        && (current_slice != /*PC_SLICE_TYPE_NTFS*/0x17))
 926       return 0;
 927
 928     if (!devread (0, 0, 512, (char *) FSYS_BUF))
 929         return 0;                       /* Cannot read superblock */
 930
 931     if(sb[3]!='N' || sb[4]!='T' || sb[5]!='F' || sb[6]!='S')
 932         return 0;
 933     blocksize = *(__u16 *)(sb+0xb);
 934     spc = *(unsigned char *)(sb+0xd);
 935     clustersize = spc * blocksize;
 936     mft_record_size = *(char *)(sb+0x40);
 937     index_record_size = *(char *)(sb+0x44);
 938     if(mft_record_size>0)
 939         mft_record_size *= clustersize;
 940     else
 941         mft_record_size = 1 << (-mft_record_size);
 942
 943     index_record_size *= clustersize;
 944     mft_record = *(__u32 *)(sb+0x30); /* only support 32 bit */
 945     spc = clustersize / 512;
 946
 947     if(mft_record_size > MAX_MFT_RECORD_SIZE || index_record_size > MAX_INDEX_RECORD_SIZE) {
 948         /* only support 1k MFT record, 4k INDEX record */
 949         return 0;
 950     }
 951
 952 #ifdef DEBUG_NTFS
 953     printf("spc=%x mft_record=%x:%x\n", spc, *(__s64 *)(sb+0x30));
 954 #endif
 955
 956     if (!devread (mft_record*spc, 0, mft_record_size, mmft->mft))
 957         return 0;                       /* Cannot read superblock */
 958
 959     if(!fixup_record( mmft->mft, "FILE", mft_record_size))
 960         return 0;
 961
 962 #ifndef NO_ALTERNATE_DATASTREAM
 963     is_ads_completion = 0;
 964 #endif
 965     if(!search_attribute(mmft, at_data, NONAME)) return 0;
 966
 967     *mft_run = mmft->runl;
 968
 969     *path_ino = FILE_ROOT;
 970
 971     return 1;
 972 }
 973
 974 int
 975 ntfs_dir (char *dirname)
 976 {
 977     char *rest, ch;
 978     int namelen;
 979     int depth = 0;
 980     int chk_sfn = 1;
 981     int flag = 0;
 982     int record_offset;
 983     int my_index_record_size;
 984     unsigned char *index_entry = 0, *entry, *index_end;
 985     int i;
 986
 987     /* main loop to find desired directory entry */
 988 loop:
 989
 990 #ifdef DEBUG_NTFS
 991     printf("dirname=%s\n", dirname);
 992 #endif
 993     if(!read_mft_record(path_ino[depth], cmft->mft, 0))
 994     {
 995 #ifdef DEBUG_NTFS
 996         printf("MFT error 1\n");
 997 #endif
 998         errnum = ERR_FSYS_CORRUPT;
 999         return 0;
1000     }
1001
1002     /* if we have a real file (and we're not just printing possibilities),
1003        then this is where we want to exit */
1004
1005     if (!*dirname || isspace (*dirname) || *dirname==':')
1006     {
1007 #ifndef STAGE1_5
1008 #ifndef NO_ALTERNATE_DATASTREAM
1009         if (*dirname==':' && print_possibilities) {
1010             char *tmp;
1011
1012             /* preparing ADS name completion */
1013             for(tmp = dirname; *tmp != '/'; tmp--);
1014             for(tmp++, rest=fnbuf; *tmp && !isspace(*tmp); *rest++ = *tmp++)
1015                 if(*tmp==':') dirname = rest;
1016             *rest++ = '\0';
1017
1018             is_ads_completion = 1;
1019             search_attribute(cmft, at_data, dirname+1);
1020             is_ads_completion = 0;
1021
1022             if(errnum==0) {
1023                 if(print_possibilities < 0)
1024                     return 1;
1025                 errnum = ERR_FILE_NOT_FOUND;
1026             }
1027             return 0;
1028         }
1029 #endif
1030 #endif
1031
1032         if (*dirname==':') dirname++;
1033         for (rest = dirname; (ch = *rest) && !isspace (ch); rest++);
1034         *rest = 0;
1035
1036 #ifdef DEBUG_NTFS
1037         printf("got file: search at_data\n");
1038 #endif
1039
1040         if (!search_attribute(cmft, at_data, dirname)) {
1041             errnum = *(dirname-1)==':'?ERR_FILE_NOT_FOUND:ERR_BAD_FILETYPE;
1042             *rest = ch;
1043             return 0;
1044         }
1045         *rest = ch;
1046
1047         filemax = cmft->attr_size;
1048 #ifdef DEBUG_NTFS
1049         printf("filemax=%x\n", filemax);
1050 #endif
1051         return 1;
1052     }
1053
1054     if(depth >= (MAX_DIR_DEPTH-1)) {
1055         errnum = ERR_FSYS_CORRUPT;
1056         return 0;
1057     }
1058
1059     /* continue with the file/directory name interpretation */
1060
1061     while (*dirname == '/')
1062         dirname++;
1063
1064     for (rest = dirname; (ch = *rest) && !isspace (ch) && ch != '/' && ch != ':'; rest++);
1065
1066     *rest = 0;
1067
1068     if (!search_attribute(cmft, at_index_root, "$I30"))
1069     {
1070         errnum = ERR_BAD_FILETYPE;
1071         return 0;
1072     }
1073
1074     read_attribute(cmft, 0, fnbuf, 16, 0);
1075     my_index_record_size = *(__u32 *)(fnbuf+8);
1076
1077     if(my_index_record_size > MAX_INDEX_RECORD_SIZE) {
1078         errnum = ERR_FSYS_CORRUPT;
1079         return 0;
1080     }
1081
1082 #ifdef DEBUG_NTFS
1083     printf("index_record_size=%x\n", my_index_record_size);
1084 #endif
1085
1086     if(cmft->attr_size > MAX_INDEX_RECORD_SIZE) {
1087         errnum = ERR_FSYS_CORRUPT;
1088         return 0;
1089     }
1090     read_attribute(cmft, 0, index_data, cmft->attr_size, 0);
1091     index_end = index_data + cmft->attr_size;
1092     index_entry = index_data + 0x20;
1093     record_offset = -1;
1094
1095 #ifndef STAGE1_5
1096     if (print_possibilities && ch != '/' && ch != ':' && !*dirname)
1097     {
1098         print_possibilities = -print_possibilities;
1099         /* fake '.' for empty directory */
1100         print_a_completion (".");
1101     }
1102 #endif
1103
1104     if (search_attribute(cmft, at_bitmap, "$I30")) {
1105         if(cmft->attr_size > MAX_INDEX_BITMAP_SIZE) {
1106             errnum = ERR_FSYS_CORRUPT;
1107             return 0;
1108         }
1109
1110         read_attribute(cmft, 0, bitmap_data, cmft->attr_size, 0);
1111
1112         if (search_attribute(cmft, at_index_allocation, "$I30")==0) {
1113             errnum = ERR_FSYS_CORRUPT;
1114             return 0;
1115         }
1116
1117         for(record_offset = 0; record_offset*my_index_record_size<cmft->attr_size; record_offset++){
1118             int bit = 1 << (record_offset&3);
1119             int byte = record_offset>>3;
1120 #ifdef DEBUG_NTFS
1121             printf("record_offset=%x\n", record_offset);
1122 #endif
1123             if((bitmap_data[byte]&bit))
1124                 break;
1125         }
1126
1127         if(record_offset*my_index_record_size>=cmft->attr_size) record_offset = -1;
1128     }
1129
1130     do
1131     {
1132         entry = index_entry; index_entry += *(__u16 *)(entry+8);
1133         if(entry+0x50>=index_entry||entry>=index_end||
1134            index_entry>=index_end||(entry[0x12]&2)){
1135             if(record_offset < 0 ||
1136                !read_attribute(cmft, record_offset*my_index_record_size, index_data, my_index_record_size, 0)){
1137                 if (!errnum)
1138                 {
1139                     if (print_possibilities < 0)
1140                     {
1141 #if 0
1142                         putchar ('\n');
1143 #endif
1144                         return 1;
1145                     }
1146
1147                     errnum = ERR_FILE_NOT_FOUND;
1148                     *rest = ch;
1149                 }
1150
1151                 return 0;
1152             }
1153             if(!fixup_record( index_data, "INDX", my_index_record_size))
1154             {
1155 #ifdef DEBUG_NTFS
1156                 printf("index error\n");
1157 #endif
1158                 errnum = ERR_FSYS_CORRUPT;
1159                 return 0;
1160             }
1161             entry = index_data + 0x18 + *(__u16 *)(index_data+0x18);
1162             index_entry = entry + *(__u16 *)(entry+8);
1163             index_end = index_data + my_index_record_size - 0x52;
1164             for(record_offset++; record_offset*my_index_record_size<cmft->attr_size; record_offset++){
1165                 int bit = 1 << (record_offset&3);
1166                 int byte = record_offset>>3;
1167                 if((bitmap_data[byte]&bit)) break;
1168             }
1169             if(record_offset*my_index_record_size>=cmft->attr_size) record_offset = -1;
1170 #ifdef DEBUG_NTFS
1171             printf("record_offset=%x\n", record_offset);
1172 #endif
1173         }
1174         flag = entry[0x51];
1175         path_ino[depth+1] = *(__u32 *)entry;
1176         if(path_ino[depth+1] < 16)
1177             continue;
1178         namelen = entry[0x50];
1179         //if(index_data[0x48]&2) printf("hidden file\n");
1180 #ifndef STAGE1_5
1181         /* skip short file name */
1182         if( flag == 2 && print_possibilities && ch != '/' && ch != ':' )
1183             continue;
1184 #endif
1185
1186         for( i = 0, entry+=0x52; i < namelen; i++, entry+=2 )
1187         {
1188             int c = *(__u16 *)entry;
1189             if(c==' '||c>=0x100)
1190                 fnbuf[i] = '_';
1191             else
1192                 fnbuf[i] = c;
1193         }
1194         fnbuf[namelen] = 0;
1195 #ifdef DEBUG_NTFS
1196         printf("FLAG: %d  NAME: %s  inum=%d\n", flag,fnbuf,path_ino[depth+1]);
1197 #endif
1198
1199         //uncntrl(fnbuf);
1200
1201         chk_sfn = nsubstring(dirname,fnbuf);
1202 #ifndef STAGE1_5
1203         if (print_possibilities && ch != '/' && ch != ':'
1204             && (!*dirname || chk_sfn <= 0))
1205         {
1206             if (print_possibilities > 0)
1207                 print_possibilities = -print_possibilities;
1208             print_a_completion (fnbuf);
1209         }
1210 #endif /* STAGE1_5 */
1211     }
1212     while (chk_sfn != 0 ||
1213            (print_possibilities && ch != '/' && ch != ':'));
1214
1215     *(dirname = rest) = ch;
1216
1217     depth++;
1218
1219     /* go back to main loop at top of function */
1220     goto loop;
1221 }
1222
1223 #ifdef DEBUG_NTFS
1224 int dump_block(char *msg, char *buf, int size){
1225     int l = (size+15)/16;
1226     int off;
1227     int i, j;
1228     int c;
1229     printf("----- %s -----\n", msg);
1230     for( i = 0, off = 0; i < l; i++, off+=16)
1231     {
1232         if(off<16)
1233             printf("000%x:", off);
1234         else if(off<256)
1235             printf("00%x:", off);
1236         else
1237             printf("0%x:", off);
1238         for(j=0;j<16;j++)
1239         {
1240             c = buf[off+j]&0xff;
1241             if( c >= 16 )
1242                 printf("%c%x",j==8?'-':' ',c);
1243             else
1244                 printf("%c0%x",j==8?'-':' ',c);
1245         }
1246         printf("  ");
1247         for(j=0;j<16;j++) {
1248             char c = buf[off+j];
1249             printf("%c",c<' '||c>='\x7f'?'.':c);
1250         }
1251         printf("\n");
1252     }
1253 }
1254 #endif
1255 #endif /* FSYS_NTFS */