ntfsprogs/utils.c

   1 /**
   2  * utils.c - Part of the Linux-NTFS project.
   3  *
   4  * Copyright (c) 2002 Richard Russon
   5  *
   6  * A set of shared functions for ntfs utilities
   7  *
   8  * This program is free software; you can redistribute it and/or modify
   9  * it under the terms of the GNU General Public License as published by
  10  * the Free Software Foundation; either version 2 of the License, or
  11  * (at your option) any later version.
  12  *
  13  * This program is distributed in the hope that it will be useful,
  14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16  * GNU General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU General Public License
  19  * along with this program (in the main directory of the Linux-NTFS
  20  * distribution in the file COPYING); if not, write to the Free Software
  21  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  22  */
  23
  24 #include <stdio.h>
  25 #include <stdarg.h>
  26 #include <errno.h>
  27 #include <sys/types.h>
  28 #include <sys/stat.h>
  29 #include <unistd.h>
  30 #include <string.h>
  31 #include <locale.h>
  32 #include <libintl.h>
  33 #include <stdlib.h>
  34 #include <limits.h>
  35
  36 #include "config.h"
  37 #include "utils.h"
  38 #include "types.h"
  39 #include "volume.h"
  40 #include "debug.h"
  41
  42 const char *ntfs_bugs = "Please report bugs to linux-ntfs-dev@lists.sourceforge.net\n";
  43 const char *ntfs_home = "Linux NTFS homepage: http://linux-ntfs.sourceforge.net\n";
  44 const char *ntfs_gpl = "This program is free software, released under the GNU "
  45         "General Public License\nand you are welcome to redistribute it under "
  46         "certain conditions.  It comes with\nABSOLUTELY NO WARRANTY; for "
  47         "details read the GNU General Public License to be\nfound in the file "
  48         "\"COPYING\" distributed with this program, or online at:\n"
  49         "http://www.gnu.org/copyleft/gpl.html\n";
  50
  51 #define NTFS_TIME_OFFSET ((s64)(369 * 365 + 89) * 24 * 3600 * 10000000)
  52
  53 /* These utilities require the following functions */
  54 extern int Eprintf (const char *format, ...) __attribute__ ((format (printf, 1, 2)));
  55 extern int Vprintf (const char *format, ...) __attribute__ ((format (printf, 1, 2)));
  56 extern int Qprintf (const char *format, ...) __attribute__ ((format (printf, 1, 2)));
  57
  58 /**
  59  * utils_set_locale
  60  */
  61 int utils_set_locale (void)
  62 {
  63         const char *locale;
  64
  65         locale = setlocale (LC_ALL, "");
  66         if (!locale) {
  67                 locale = setlocale (LC_ALL, NULL);
  68                 Eprintf ("Failed to set locale, using default '%s'.\n", locale);
  69                 return 1;
  70         } else {
  71                 Vprintf ("Using locale '%s'.\n", locale);
  72                 return 0;
  73         }
  74 }
  75
  76 /**
  77  * utils_valid_device - Perform some safety checks on the device, before we start
  78  * @name:   Full pathname of the device/file to work with
  79  * @force:  Continue regardless of problems
  80  *
  81  * Check that the name refers to a device and that is isn't already mounted.
  82  * These checks can be overridden by using the force option.
  83  *
  84  * Return:  1  Success, we can continue
  85  *          0  Error, we cannot use this device
  86  */
  87 int utils_valid_device (const char *name, int force)
  88 {
  89         unsigned long mnt_flags = 0;
  90         struct stat st;
  91
  92         if (stat (name, &st) == -1) {
  93                 if (errno == ENOENT) {
  94                         Eprintf ("The device %s doesn't exist\n", name);
  95                 } else {
  96                         Eprintf ("Error getting information about %s: %s\n", name, strerror (errno));
  97                 }
  98                 return 0;
  99         }
 100
 101         if (!S_ISBLK (st.st_mode)) {
 102                 Vprintf ("%s is not a block device.\n", name);
 103                 if (!force) {
 104                         Eprintf ("Use the force option to work with files.\n");
 105                         return 0;
 106                 }
 107                 Vprintf ("Forced to continue.\n");
 108         }
 109
 110         /* Make sure the file system is not mounted. */
 111         if (ntfs_check_if_mounted (name, &mnt_flags)) {
 112                 Vprintf ("Failed to determine whether %s is mounted: %s\n", name, strerror (errno));
 113                 if (!force) {
 114                         Eprintf ("Use the force option to ignore this error.\n");
 115                         return 0;
 116                 }
 117                 Vprintf ("Forced to continue.\n");
 118         } else if (mnt_flags & NTFS_MF_MOUNTED) {
 119                 Vprintf ("The device %s, is mounted.\n", name);
 120                 if (!force) {
 121                         Eprintf ("Use the force option to work a mounted filesystem.\n");
 122                         return 0;
 123                 }
 124                 Vprintf ("Forced to continue.\n");
 125         }
 126
 127         return 1;
 128 }
 129
 130 /**
 131  * utils_mount_volume
 132  */
 133 ntfs_volume * utils_mount_volume (const char *device, unsigned long flags, BOOL force)
 134 {
 135         ntfs_volume *vol;
 136
 137         if (!device)
 138                 return NULL;
 139
 140         if (!utils_valid_device (device, force))
 141                 return NULL;
 142
 143         vol = ntfs_mount (device, MS_RDONLY);
 144         if (!vol) {
 145                 Eprintf ("Couldn't mount device '%s': %s\n", device, strerror (errno));
 146                 return NULL;
 147         }
 148
 149         if (vol->flags & VOLUME_IS_DIRTY) {
 150                 Qprintf ("Volume is dirty.\n");
 151                 if (!force) {
 152                         Eprintf ("Run chkdsk and try again, or use the --force option.\n");
 153                         ntfs_umount (vol, FALSE);
 154                         return NULL;
 155                 }
 156                 Qprintf ("Forced to continue.\n");
 157         }
 158
 159         return vol;
 160 }
 161
 162 /**
 163  * utils_parse_size - Convert a string representing a size
 164  * @value:  String to be parsed
 165  * @size:   Parsed size
 166  * @scale:  XXX FIXME
 167  *
 168  * Read a string and convert it to a number.  Strings may be suffixed to scale
 169  * them.  Any number without a suffix is assumed to be in bytes.
 170  *
 171  * Suffix  Description  Multiple
 172  *  [tT]    Terabytes     10^12
 173  *  [gG]    Gigabytes     10^9
 174  *  [mM]    Megabytes     10^6
 175  *  [kK]    Kilobytes     10^3
 176  *
 177  * Notes:
 178  *     Only the first character of the suffix is read.
 179  *     The multipliers are decimal thousands, not binary: 1000, not 1024.
 180  *     If parse_size fails, @size will not be changed
 181  *
 182  * Return:  1  Success
 183  *          0  Error, the string was malformed
 184  */
 185 int utils_parse_size (const char *value, s64 *size, BOOL scale)
 186 {
 187         long long result;
 188         char *suffix = NULL;
 189
 190         if (!value || !size)
 191                 return 0;
 192
 193         Dprintf ("Parsing size '%s'.\n", value);
 194
 195         result = strtoll (value, &suffix, 10);
 196         if (result < 0 || errno == ERANGE) {
 197                 Eprintf ("Invalid size '%s'.\n", value);
 198                 return 0;
 199         }
 200
 201         if (!suffix) {
 202                 Eprintf ("Internal error, strtoll didn't return a suffix.\n");
 203                 return 0;
 204         }
 205
 206         if (scale) {
 207                 switch (suffix[0]) {
 208                         case 't': case 'T': result *= 1000;
 209                         case 'g': case 'G': result *= 1000;
 210                         case 'm': case 'M': result *= 1000;
 211                         case 'k': case 'K': result *= 1000;
 212                         case '-': case 0:
 213                                 break;
 214                         default:
 215                                 Eprintf ("Invalid size suffix '%s'.  Use T, G, M, or K.\n", suffix);
 216                                 return 0;
 217                 }
 218         } else {
 219                 if ((suffix[0] != '-') && (suffix[0] != 0)) {
 220                         Eprintf ("Invalid number '%.*s'.\n", (suffix - value + 1), value);
 221                         return 0;
 222                 }
 223         }
 224
 225         Dprintf ("Parsed size = %lld.\n", result);
 226         *size = result;
 227         return 1;
 228 }
 229
 230 /**
 231  * utils_parse_range - Convert a string representing a range of numbers
 232  * @string:  The string to be parsed
 233  * @start:   The beginning of the range will be stored here
 234  * @finish:  The end of the range will be stored here
 235  *
 236  * Read a string of the form n-m.  If the lower end is missing, zero will be
 237  * substituted.  If the upper end is missing LONG_MAX will be used.  If the
 238  * string cannot be parsed correctly, @start and @finish will not be changed.
 239  *
 240  * Return:  1  Success, a valid string was found
 241  *          0  Error, the string was not a valid range
 242  */
 243 int utils_parse_range (const char *string, s64 *start, s64 *finish, BOOL scale)
 244 {
 245         s64 a, b;
 246         char *middle;
 247
 248         if (!string || !start || !finish)
 249                 return 0;
 250
 251         middle = strchr (string, '-');
 252         if (string == middle) {
 253                 Dprintf ("Range has no beginning, defaulting to 0.\n");
 254                 a = 0;
 255         } else {
 256                 if (!utils_parse_size (string, &a, scale))
 257                         return 0;
 258         }
 259
 260         if (middle) {
 261                 if (middle[1] == 0) {
 262                         b = LONG_MAX;           // XXX ULLONG_MAX
 263                         Dprintf ("Range has no end, defaulting to %lld.\n", b);
 264                 } else {
 265                         if (!utils_parse_size (middle+1, &b, scale))
 266                                 return 0;
 267                 }
 268         } else {
 269                 b = a;
 270         }
 271
 272         Dprintf ("Range '%s' = %lld - %lld\n", string, a, b);
 273
 274         *start  = a;
 275         *finish = b;
 276         return 1;
 277 }
 278
 279 /**
 280  * ntfs2utc - Convert an NTFS time to Unix time
 281  * @time:  An NTFS time in 100ns units since 1601
 282  *
 283  * NTFS stores times as the number of 100ns intervals since January 1st 1601 at
 284  * 00:00 UTC.  This system will not suffer from Y2K problems until ~57000AD.
 285  *
 286  * Return:  n  A Unix time (number of seconds since 1970)
 287  */
 288 time_t ntfs2utc (s64 time)
 289 {
 290         return (time - (NTFS_TIME_OFFSET)) / 10000000;
 291 }
 292
 293 /**
 294  * utc2ntfs - convert Linux time to NTFS time
 295  * @time:  Linux time to convert to NTFS
 296  *
 297  * Convert the Linux time @time to its corresponding NTFS time.
 298  *
 299  * Linux stores time in a long at present and measures it as the number of
 300  * 1-second intervals since 1st January 1970, 00:00:00 UTC.
 301  *
 302  * NTFS uses Microsoft's standard time format which is stored in a s64 and is
 303  * measured as the number of 100 nano-second intervals since 1st January 1601,
 304  * 00:00:00 UTC.
 305  *
 306  * Return:  n  An NTFS time (100ns units since Jan 1601)
 307  */
 308 s64 utc2ntfs (time_t time)
 309 {
 310         /* Convert to 100ns intervals and then add the NTFS time offset. */
 311         return (s64)time * 10000000 + NTFS_TIME_OFFSET;
 312 }
 313
 314 /**
 315  * find_attribute - Find an attribute of the given type
 316  * @type:  An attribute type, e.g. AT_FILE_NAME
 317  * @ctx:   A search context, created using ntfs_get_attr_search_ctx
 318  *
 319  * Using the search context to keep track, find the first/next occurrence of a
 320  * given attribute type.
 321  *
 322  * N.B.  This will return a pointer into @mft.  As long as the search context
 323  *       has been created without an inode, it won't overflow the buffer.
 324  *
 325  * Return:  Pointer  Success, an attribute was found
 326  *          NULL     Error, no matching attributes were found
 327  */
 328 ATTR_RECORD * find_attribute (const ATTR_TYPES type, ntfs_attr_search_ctx *ctx)
 329 {
 330         if (!ctx)
 331                 return NULL;
 332
 333         if (ntfs_attr_lookup(type, NULL, 0, 0, 0, NULL, 0, ctx) != 0) {
 334                 Dprintf ("find_attribute didn't find an attribute of type: 0x%02x.\n", type);
 335                 return NULL;    /* None / no more of that type */
 336         }
 337
 338         Dprintf ("find_attribute found an attribute of type: 0x%02x.\n", type);
 339         return ctx->attr;
 340 }
 341
 342 /**
 343  * find_first_attribute - Find the first attribute of a given type
 344  * @type:  An attribute type, e.g. AT_FILE_NAME
 345  * @mft:   A buffer containing a raw MFT record
 346  *
 347  * Search through a raw MFT record for an attribute of a given type.
 348  * The return value is a pointer into the MFT record that was supplied.
 349  *
 350  * N.B.  This will return a pointer into @mft.  The pointer won't stray outside
 351  *       the buffer, since we created the search context without an inode.
 352  *
 353  * Return:  Pointer  Success, an attribute was found
 354  *          NULL     Error, no matching attributes were found
 355  */
 356 ATTR_RECORD * find_first_attribute (const ATTR_TYPES type, MFT_RECORD *mft)
 357 {
 358         ntfs_attr_search_ctx *ctx;
 359         ATTR_RECORD *rec;
 360
 361         if (!mft)
 362                 return NULL;
 363
 364         ctx = ntfs_attr_get_search_ctx (NULL, mft);
 365         if (!ctx) {
 366                 Eprintf ("Couldn't create a search context.\n");
 367                 return NULL;
 368         }
 369
 370         rec = find_attribute (type, ctx);
 371         ntfs_attr_put_search_ctx (ctx);
 372         if (rec)
 373                 Dprintf ("find_first_attribute: found attr of type 0x%02x.\n", type);
 374         else
 375                 Dprintf ("find_first_attribute: didn't find attr of type 0x%02x.\n", type);
 376         return rec;
 377 }
 378
 379 /**
 380  * utils_inode_get_name
 381  *
 382  * using inode
 383  * get filename
 384  * add name to list
 385  * get parent
 386  * if parent is 5 (/) stop
 387  * get inode of parent
 388  */
 389 int utils_inode_get_name (ntfs_inode *inode, char *buffer, int bufsize)
 390 {
 391         // XXX option: names = posix/win32 or dos
 392         // flags: path, filename, or both
 393         const int max_path = 20;
 394
 395         ntfs_volume *vol;
 396         ntfs_attr_search_ctx *ctx;
 397         ATTR_RECORD *rec;
 398         FILE_NAME_ATTR *attr;
 399         int name_space;
 400         MFT_REF parent = FILE_root;
 401         char *names[max_path + 1];// XXX malloc? and make max bigger?
 402         int i, len, offset = 0;
 403
 404         if (!inode || !buffer)
 405                 return 0;
 406
 407         vol = inode->vol;
 408
 409         //printf ("sizeof (char*) = %d, sizeof (names) = %d\n", sizeof (char*), sizeof (names));
 410         memset (names, 0, sizeof (names));
 411
 412         for (i = 0; i < max_path; i++) {
 413
 414                 ctx = ntfs_attr_get_search_ctx (inode, NULL);
 415                 if (!ctx) {
 416                         Eprintf ("Couldn't create a search context.\n");
 417                         return 0;
 418                 }
 419
 420                 //printf ("i = %d, inode = %p (%lld)\n", i, inode, inode->mft_no);
 421
 422                 name_space = 4;
 423                 while ((rec = find_attribute (AT_FILE_NAME, ctx))) {
 424                         /* We know this will always be resident. */
 425                         attr = (FILE_NAME_ATTR *) ((char *) rec + le16_to_cpu (rec->value_offset));
 426
 427                         if (attr->file_name_type >= name_space) { //XXX find the ...
 428                                 continue;
 429                         }
 430
 431                         name_space = attr->file_name_type;
 432                         parent     = le64_to_cpu (attr->parent_directory);
 433
 434                         if (names[i]) {
 435                                 free (names[i]);
 436                                 names[i] = NULL;
 437                         }
 438
 439                         if (ntfs_ucstombs (attr->file_name, attr->file_name_length,
 440                             &names[i], attr->file_name_length) < 0) {
 441                                 char *temp;
 442                                 Eprintf ("Couldn't translate filename to current locale.\n");
 443                                 temp = malloc (30);
 444                                 if (!temp)
 445                                         return 0;
 446                                 snprintf (temp, 30, "<MFT%lld>", inode->mft_no);
 447                                 names[i] = temp;
 448                         }
 449
 450                         //printf ("names[%d] %s\n", i, names[i]);
 451                         //printf ("parent = %lld\n", MREF (parent));
 452                 }
 453
 454                 ntfs_attr_put_search_ctx(ctx);
 455
 456                 if (i > 0)                      /* Don't close the original inode */
 457                         ntfs_inode_close (inode);
 458
 459                 if (MREF (parent) == FILE_root) {       /* The root directory, stop. */
 460                         //printf ("inode 5\n");
 461                         break;
 462                 }
 463
 464                 inode = ntfs_inode_open (vol, parent);
 465                 if (!inode) {
 466                         Eprintf ("Couldn't open inode %lld.\n", MREF (parent));
 467                         break;
 468                 }
 469         }
 470
 471         if (i >= max_path) {
 472                 /* If we get into an infinite loop, we'll end up here. */
 473                 Eprintf ("The directory structure is too deep (over %d) nested directories.\n", max_path);
 474                 return 0;
 475         }
 476
 477         /* Assemble the names in the correct order. */
 478         for (i = max_path; i >= 0; i--) {
 479                 if (!names[i])
 480                         continue;
 481
 482                 len = snprintf (buffer + offset, bufsize - offset, "%c%s", PATH_SEP, names[i]);
 483                 if (len >= (bufsize - offset)) {
 484                         Eprintf ("Pathname was truncated.\n");
 485                         break;
 486                 }
 487
 488                 offset += len;
 489         }
 490
 491         /* Free all the allocated memory */
 492         for (i = 0; i < max_path; i++)
 493                 free (names[i]);
 494
 495         Dprintf ("Pathname: %s\n", buffer);
 496
 497         return 0;
 498 }
 499
 500 /**
 501  * utils_attr_get_name
 502  */
 503 int utils_attr_get_name (ntfs_volume *vol, ATTR_RECORD *attr, char *buffer, int bufsize)
 504 {
 505         int len, namelen, offset = 0;
 506         char *name = NULL;
 507         ATTR_DEF *attrdef;
 508
 509         // flags: attr, name, or both
 510         if (!attr || !buffer)
 511                 return 0;
 512
 513         attrdef = ntfs_attr_find_in_attrdef (vol, attr->type);
 514         if (attrdef) {
 515                 namelen = ntfs_ucsnlen (attrdef->name, sizeof (attrdef->name));
 516                 if (ntfs_ucstombs (attrdef->name, namelen, &name, namelen) < 0) {
 517                         Eprintf ("Couldn't translate attribute type to current locale.\n");
 518                         // <UNKNOWN>?
 519                         return 0;
 520                 }
 521                 len = snprintf (buffer, bufsize, "%s", name);
 522         } else {
 523                 Eprintf ("Unknown attribute type 0x%02x\n", attr->type);
 524                 len = snprintf (buffer, bufsize, "<UNKNOWN>");
 525         }
 526
 527         if (len >= bufsize) {
 528                 Eprintf ("Attribute type was truncated.\n");
 529                 return 0;
 530         }
 531
 532         offset += len;
 533
 534         if (!attr->name_length) {
 535                 return 0;
 536         }
 537
 538         namelen = attr->name_length;
 539         if (ntfs_ucstombs ((uchar_t *)((char *)attr + attr->name_offset),
 540             namelen, &name, namelen) < 0) {
 541                 Eprintf ("Couldn't translate attribute name to current locale.\n");
 542                 // <UNKNOWN>?
 543                 return 0;
 544         }
 545
 546         len = snprintf (buffer + offset, bufsize - offset, "(%s)", name);
 547         free (name);
 548
 549         if ((len + offset) >= bufsize) {
 550                 Eprintf ("Attribute name was truncated.\n");
 551                 return 0;
 552         }
 553
 554         return 0;
 555 }
 556
 557 /**
 558  * utils_cluster_in_use - Determine if a cluster is in use
 559  * @vol:  An ntfs volume obtained from ntfs_mount
 560  * @lcn:  The Logical Cluster Number to test
 561  *
 562  * The metadata file $Bitmap has one binary bit representing each cluster on
 563  * disk.  The bit will be set for each cluster that is in use.  The function
 564  * reads the relevant part of $Bitmap into a buffer and tests the bit.
 565  *
 566  * This function has a static buffer in which it caches a section of $Bitmap.
 567  * If the lcn, being tested, lies outside the range, the buffer will be
 568  * refreshed.
 569  *
 570  * Return:  1  Cluster is in use
 571  *          0  Cluster is free space
 572  *         -1  Error occurred
 573  */
 574 int utils_cluster_in_use (ntfs_volume *vol, long long lcn)
 575 {
 576         static unsigned char buffer[512];
 577         static long long bmplcn = -sizeof (buffer) - 1; /* Which bit of $Bitmap is in the buffer */
 578
 579         int byte, bit;
 580         ntfs_attr *attr;
 581
 582         if (!vol)
 583                 return -1;
 584
 585         /* Does lcn lie in the section of $Bitmap we already have cached? */
 586         if ((lcn < bmplcn) || (lcn >= (bmplcn + (sizeof (buffer) << 3)))) {
 587                 Dprintf ("Bit lies outside cache.\n");
 588                 attr = ntfs_attr_open (vol->lcnbmp_ni, AT_DATA, NULL, 0);
 589                 if (!attr) {
 590                         Eprintf ("Couldn't open $Bitmap: %s\n", strerror (errno));
 591                         return -1;
 592                 }
 593
 594                 /* Mark the buffer as in use, in case the read is shorter. */
 595                 memset (buffer, 0xFF, sizeof (buffer));
 596                 bmplcn = lcn & (~((sizeof (buffer) << 3) - 1));
 597
 598                 if (ntfs_attr_pread (attr, (bmplcn>>3), sizeof (buffer), buffer) < 0) {
 599                         Eprintf ("Couldn't read $Bitmap: %s\n", strerror (errno));
 600                         ntfs_attr_close (attr);
 601                         return -1;
 602                 }
 603
 604                 Dprintf ("Reloaded bitmap buffer.\n");
 605                 ntfs_attr_close (attr);
 606         }
 607
 608         bit  = 1 << (lcn & 7);
 609         byte = (lcn >> 3) & (sizeof (buffer) - 1);
 610         Dprintf ("cluster = %lld, bmplcn = %lld, byte = %d, bit = %d, in use %d\n",
 611                 lcn, bmplcn, byte, bit, buffer[byte] & bit);
 612
 613         return (buffer[byte] & bit);
 614 }
 615
 616 /**
 617  * utils_mftrec_in_use - Determine if a MFT Record is in use
 618  * @vol:   An ntfs volume obtained from ntfs_mount
 619  * @mref:  MFT Reference (inode number)
 620  *
 621  * The metadata file $BITMAP has one binary bit representing each record in the
 622  * MFT.  The bit will be set for each record that is in use.  The function
 623  * reads the relevant part of $BITMAP into a buffer and tests the bit.
 624  *
 625  * This function has a static buffer in which it caches a section of $BITMAP.
 626  * If the mref, being tested, lies outside the range, the buffer will be
 627  * refreshed.
 628  *
 629  * Return:  1  MFT Record is in use
 630  *          0  MFT Record is unused
 631  *         -1  Error occurred
 632  */
 633 int utils_mftrec_in_use (ntfs_volume *vol, MFT_REF mref)
 634 {
 635         static u8 buffer[512];
 636         static s64 bmpmref = -sizeof (buffer) - 1; /* Which bit of $BITMAP is in the buffer */
 637
 638         int byte, bit;
 639
 640         if (!vol)
 641                 return -1;
 642
 643         /* Does mref lie in the section of $Bitmap we already have cached? */
 644         if ((mref < bmpmref) || (mref >= (bmpmref + (sizeof (buffer) << 3)))) {
 645                 Dprintf ("Bit lies outside cache.\n");
 646
 647                 /* Mark the buffer as not in use, in case the read is shorter. */
 648                 memset (buffer, 0, sizeof (buffer));
 649                 bmpmref = mref & (~((sizeof (buffer) << 3) - 1));
 650
 651                 if (ntfs_attr_pread (vol->mftbmp_na, (bmpmref>>3), sizeof (buffer), buffer) < 0) {
 652                         Eprintf ("Couldn't read $MFT/$BITMAP: %s\n", strerror (errno));
 653                         return -1;
 654                 }
 655
 656                 Dprintf ("Reloaded bitmap buffer.\n");
 657         }
 658
 659         bit  = 1 << (mref & 7);
 660         byte = (mref >> 3) & (sizeof (buffer) - 1);
 661         Dprintf ("cluster = %lld, bmpmref = %lld, byte = %d, bit = %d, in use %d\n",
 662                 mref, bmpmref, byte, bit, buffer[byte] & bit);
 663
 664         return (buffer[byte] & bit);
 665 }
 666
 667
 668 #if 0
 669 hamming weight
 670 inline unsigned int hweight32(unsigned int w)
 671 {
 672         unsigned int res = (w & 0x55555555) + ((w >> 1) & 0x55555555);
 673         res = (res & 0x33333333) + ((res >> 2) & 0x33333333);
 674         res = (res & 0x0F0F0F0F) + ((res >> 4) & 0x0F0F0F0F);
 675         res = (res & 0x00FF00FF) + ((res >> 8) & 0x00FF00FF);
 676         return (res & 0x0000FFFF) + ((res >> 16) & 0x0000FFFF);
 677 }
 678
 679 inline unsigned int hweight16(unsigned int w)
 680 {
 681         unsigned int res = (w & 0x5555) + ((w >> 1) & 0x5555);
 682         res = (res & 0x3333) + ((res >> 2) & 0x3333);
 683         res = (res & 0x0F0F) + ((res >> 4) & 0x0F0F);
 684         return (res & 0x00FF) + ((res >> 8) & 0x00FF);
 685 }
 686
 687 inline unsigned int hweight8(unsigned int w)
 688 {
 689         unsigned int res = (w & 0x55) + ((w >> 1) & 0x55);
 690         res = (res & 0x33) + ((res >> 2) & 0x33);
 691         return (res & 0x0F) + ((res >> 4) & 0x0F);
 692 }
 693
 694 inline int set_bit(int nr,long * addr)
 695 {
 696         int     mask, retval;
 697
 698         addr += nr >> 5;
 699         mask = 1 << (nr & 0x1f);
 700         retval = (mask & *addr) != 0;
 701         *addr |= mask;
 702         return retval;
 703 }
 704
 705 inline int clear_bit(int nr, long * addr)
 706 {
 707         int     mask, retval;
 708
 709         addr += nr >> 5;
 710         mask = 1 << (nr & 0x1f);
 711         retval = (mask & *addr) != 0;
 712         *addr &= ~mask;
 713         return retval;
 714 }
 715
 716 inline int test_bit(int nr, long * addr)
 717 {
 718         int     mask;
 719
 720         addr += nr >> 5;
 721         mask = 1 << (nr & 0x1f);
 722         return ((mask & *addr) != 0);
 723 }
 724
 725 #endif
 726