fs/ntfscomp.c

   1 /* ntfscomp.c - compression support for the NTFS filesystem */
   2 /*
   3  *  Copyright (C) 2007 Free Software Foundation, Inc.
   4  *
   5  *  This program is free software: you can redistribute it and/or modify
   6  *  it under the terms of the GNU General Public License as published by
   7  *  the Free Software Foundation, either version 3 of the License, or
   8  *  (at your option) any later version.
   9  *
  10  *  This program is distributed in the hope that it will be useful,
  11  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  *  GNU General Public License for more details.
  14  *
  15  *  You should have received a copy of the GNU General Public License
  16  *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
  17  */
  18
  19 #include <grub/file.h>
  20 #include <grub/mm.h>
  21 #include <grub/misc.h>
  22 #include <grub/disk.h>
  23 #include <grub/dl.h>
  24 #include <grub/fshelp.h>
  25 #include <grub/ntfs.h>
  26
  27 static grub_err_t
  28 decomp_nextvcn (struct grub_ntfs_comp *cc)
  29 {
  30   if (cc->comp_head >= cc->comp_tail)
  31     return grub_error (GRUB_ERR_BAD_FS, "Compression block overflown");
  32   if (grub_disk_read
  33       (cc->disk,
  34        (cc->comp_table[cc->comp_head][1] -
  35         (cc->comp_table[cc->comp_head][0] - cc->cbuf_vcn)) * cc->spc, 0,
  36        cc->spc << BLK_SHR, cc->cbuf))
  37     return grub_errno;
  38   cc->cbuf_vcn++;
  39   if ((cc->cbuf_vcn >= cc->comp_table[cc->comp_head][0]))
  40     cc->comp_head++;
  41   cc->cbuf_ofs = 0;
  42   return 0;
  43 }
  44
  45 static grub_err_t
  46 decomp_getch (struct grub_ntfs_comp *cc, unsigned char *res)
  47 {
  48   if (cc->cbuf_ofs >= (cc->spc << BLK_SHR))
  49     {
  50       if (decomp_nextvcn (cc))
  51         return grub_errno;
  52     }
  53   *res = (unsigned char) cc->cbuf[cc->cbuf_ofs++];
  54   return 0;
  55 }
  56
  57 static grub_err_t
  58 decomp_get16 (struct grub_ntfs_comp *cc, grub_uint16_t * res)
  59 {
  60   unsigned char c1, c2;
  61
  62   if ((decomp_getch (cc, &c1)) || (decomp_getch (cc, &c2)))
  63     return grub_errno;
  64   *res = ((grub_uint16_t) c2) * 256 + ((grub_uint16_t) c1);
  65   return 0;
  66 }
  67
  68 /* Decompress a block (4096 bytes) */
  69 static grub_err_t
  70 decomp_block (struct grub_ntfs_comp *cc, char *dest)
  71 {
  72   grub_uint16_t flg, cnt;
  73
  74   if (decomp_get16 (cc, &flg))
  75     return grub_errno;
  76   cnt = (flg & 0xFFF) + 1;
  77
  78   if (dest)
  79     {
  80       if (flg & 0x8000)
  81         {
  82           unsigned char tag;
  83           grub_uint32_t bits, copied;
  84
  85           bits = copied = tag = 0;
  86           while (cnt > 0)
  87             {
  88               if (copied > COM_LEN)
  89                 return grub_error (GRUB_ERR_BAD_FS,
  90                                    "Compression block too large");
  91
  92               if (!bits)
  93                 {
  94                   if (decomp_getch (cc, &tag))
  95                     return grub_errno;
  96
  97                   bits = 8;
  98                   cnt--;
  99                   if (cnt <= 0)
 100                     break;
 101                 }
 102               if (tag & 1)
 103                 {
 104                   grub_uint32_t i, len, delta, code, lmask, dshift;
 105                   grub_uint16_t word;
 106
 107                   if (decomp_get16 (cc, &word))
 108                     return grub_errno;
 109
 110                   code = word;
 111                   cnt -= 2;
 112
 113                   if (!copied)
 114                     {
 115                       grub_error (GRUB_ERR_BAD_FS, "Context window empty");
 116                       return 0;
 117                     }
 118
 119                   for (i = copied - 1, lmask = 0xFFF, dshift = 12; i >= 0x10;
 120                        i >>= 1)
 121                     {
 122                       lmask >>= 1;
 123                       dshift--;
 124                     }
 125
 126                   delta = code >> dshift;
 127                   len = (code & lmask) + 3;
 128
 129                   for (i = 0; i < len; i++)
 130                     {
 131                       dest[copied] = dest[copied - delta - 1];
 132                       copied++;
 133                     }
 134                 }
 135               else
 136                 {
 137                   unsigned char ch;
 138
 139                   if (decomp_getch (cc, &ch))
 140                     return grub_errno;
 141                   dest[copied++] = ch;
 142                   cnt--;
 143                 }
 144               tag >>= 1;
 145               bits--;
 146             }
 147           return 0;
 148         }
 149       else
 150         {
 151           if (cnt != COM_LEN)
 152             return grub_error (GRUB_ERR_BAD_FS,
 153                                "Invalid compression block size");
 154         }
 155     }
 156
 157   while (cnt > 0)
 158     {
 159       int n;
 160
 161       n = (cc->spc << BLK_SHR) - cc->cbuf_ofs;
 162       if (n > cnt)
 163         n = cnt;
 164       if ((dest) && (n))
 165         {
 166           memcpy (dest, &cc->cbuf[cc->cbuf_ofs], n);
 167           dest += n;
 168         }
 169       cnt -= n;
 170       cc->cbuf_ofs += n;
 171       if ((cnt) && (decomp_nextvcn (cc)))
 172         return grub_errno;
 173     }
 174   return 0;
 175 }
 176
 177 static grub_err_t
 178 read_block (struct grub_ntfs_rlst *ctx, char *buf, int num)
 179 {
 180   int cpb = COM_SEC / ctx->comp.spc;
 181
 182   while (num)
 183     {
 184       int nn;
 185
 186       if ((ctx->target_vcn & 0xF) == 0)
 187         {
 188
 189           if (ctx->comp.comp_head != ctx->comp.comp_tail)
 190             return grub_error (GRUB_ERR_BAD_FS, "Invalid compression block");
 191           ctx->comp.comp_head = ctx->comp.comp_tail = 0;
 192           ctx->comp.cbuf_vcn = ctx->target_vcn;
 193           ctx->comp.cbuf_ofs = (ctx->comp.spc << BLK_SHR);
 194           if (ctx->target_vcn >= ctx->next_vcn)
 195             {
 196               if (grub_ntfs_read_run_list (ctx))
 197                 return grub_errno;
 198             }
 199           while (ctx->target_vcn + 16 > ctx->next_vcn)
 200             {
 201               if (ctx->flags & RF_BLNK)
 202                 break;
 203               ctx->comp.comp_table[ctx->comp.comp_tail][0] = ctx->next_vcn;
 204               ctx->comp.comp_table[ctx->comp.comp_tail][1] =
 205                 ctx->curr_lcn + ctx->next_vcn - ctx->curr_vcn;
 206               ctx->comp.comp_tail++;
 207               if (grub_ntfs_read_run_list (ctx))
 208                 return grub_errno;
 209             }
 210         }
 211
 212       nn = (16 - (ctx->target_vcn & 0xF)) / cpb;
 213       if (nn > num)
 214         nn = num;
 215       num -= nn;
 216
 217       if (ctx->flags & RF_BLNK)
 218         {
 219           ctx->target_vcn += nn * cpb;
 220           if (ctx->comp.comp_tail == 0)
 221             {
 222               if (buf)
 223                 {
 224                   grub_memset (buf, 0, nn * COM_LEN);
 225                   buf += nn * COM_LEN;
 226                 }
 227             }
 228           else
 229             {
 230               while (nn)
 231                 {
 232                   if (decomp_block (&ctx->comp, buf))
 233                     return grub_errno;
 234                   if (buf)
 235                     buf += COM_LEN;
 236                   nn--;
 237                 }
 238             }
 239         }
 240       else
 241         {
 242           nn *= cpb;
 243           while ((ctx->comp.comp_head < ctx->comp.comp_tail) && (nn))
 244             {
 245               int tt;
 246
 247               tt =
 248                 ctx->comp.comp_table[ctx->comp.comp_head][0] -
 249                 ctx->target_vcn;
 250               if (tt > nn)
 251                 tt = nn;
 252               ctx->target_vcn += tt;
 253               if (buf)
 254                 {
 255                   if (grub_disk_read
 256                       (ctx->comp.disk,
 257                        (ctx->comp.comp_table[ctx->comp.comp_head][1] -
 258                         (ctx->comp.comp_table[ctx->comp.comp_head][0] -
 259                          ctx->target_vcn)) * ctx->comp.spc, 0,
 260                        tt * (ctx->comp.spc << BLK_SHR), buf))
 261                     return grub_errno;
 262                   buf += tt * (ctx->comp.spc << BLK_SHR);
 263                 }
 264               nn -= tt;
 265               if (ctx->target_vcn >=
 266                   ctx->comp.comp_table[ctx->comp.comp_head][0])
 267                 ctx->comp.comp_head++;
 268             }
 269           if (nn)
 270             {
 271               if (buf)
 272                 {
 273                   if (grub_disk_read
 274                       (ctx->comp.disk,
 275                        (ctx->target_vcn - ctx->curr_vcn +
 276                         ctx->curr_lcn) * ctx->comp.spc, 0,
 277                        nn * (ctx->comp.spc << BLK_SHR), buf))
 278                     return grub_errno;
 279                   buf += nn * (ctx->comp.spc << BLK_SHR);
 280                 }
 281               ctx->target_vcn += nn;
 282             }
 283         }
 284     }
 285   return 0;
 286 }
 287
 288 static grub_err_t
 289 ntfscomp (struct grub_ntfs_attr *at, char *dest, grub_uint32_t ofs,
 290           grub_uint32_t len, struct grub_ntfs_rlst *ctx, grub_uint32_t vcn)
 291 {
 292   grub_err_t ret;
 293
 294   ctx->comp.comp_head = ctx->comp.comp_tail = 0;
 295   ctx->comp.cbuf = grub_malloc ((ctx->comp.spc) << BLK_SHR);
 296   if (!ctx->comp.cbuf)
 297     return 0;
 298
 299   ret = 0;
 300
 301   //ctx->comp.disk->read_hook = read_hook;
 302
 303   if ((vcn > ctx->target_vcn) &&
 304       (read_block
 305        (ctx, NULL, ((vcn - ctx->target_vcn) * ctx->comp.spc) / COM_SEC)))
 306     {
 307       ret = grub_errno;
 308       goto quit;
 309     }
 310
 311   if (ofs % COM_LEN)
 312     {
 313       grub_uint32_t t, n, o;
 314
 315       t = ctx->target_vcn * (ctx->comp.spc << BLK_SHR);
 316       if (read_block (ctx, at->sbuf, 1))
 317         {
 318           ret = grub_errno;
 319           goto quit;
 320         }
 321
 322       at->save_pos = t;
 323
 324       o = ofs % COM_LEN;
 325       n = COM_LEN - o;
 326       if (n > len)
 327         n = len;
 328       grub_memcpy (dest, &at->sbuf[o], n);
 329       if (n == len)
 330         goto quit;
 331       dest += n;
 332       len -= n;
 333     }
 334
 335   if (read_block (ctx, dest, len / COM_LEN))
 336     {
 337       ret = grub_errno;
 338       goto quit;
 339     }
 340
 341   dest += (len / COM_LEN) * COM_LEN;
 342   len = len % COM_LEN;
 343   if (len)
 344     {
 345       grub_uint32_t t;
 346
 347       t = ctx->target_vcn * (ctx->comp.spc << BLK_SHR);
 348       if (read_block (ctx, at->sbuf, 1))
 349         {
 350           ret = grub_errno;
 351           goto quit;
 352         }
 353
 354       at->save_pos = t;
 355
 356       grub_memcpy (dest, at->sbuf, len);
 357     }
 358
 359 quit:
 360   //ctx->comp.disk->read_hook = 0;
 361   if (ctx->comp.cbuf)
 362     grub_free (ctx->comp.cbuf);
 363   return ret;
 364 }
 365
 366 GRUB_MOD_INIT (ntfscomp)
 367 {
 368   grub_ntfscomp_func = ntfscomp;
 369 }
 370
 371 GRUB_MOD_FINI (ntfscomp)
 372 {
 373   grub_ntfscomp_func = NULL;
 374 }