src/vfsck/ufs_tables.c

   1 /*
   2  * Copyright (c) 1982, 1986 Regents of the University of California.
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms are permitted
   6  * provided that the above copyright notice and this paragraph are
   7  * duplicated in all such forms and that any documentation,
   8  * advertising materials, and other materials related to such
   9  * distribution and use acknowledge that the software was developed
  10  * by the University of California, Berkeley.  The name of the
  11  * University may not be used to endorse or promote products derived
  12  * from this software without specific prior written permission.
  13  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
  14  * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
  15  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  16  *
  17  *      @(#)ufs_tables.c        7.3 (Berkeley) 4/24/89
  18  */
  19
  20 #include <afs/param.h>
  21 #include <afsconfig.h>
  22
  23 RCSID("$Header$");
  24
  25 #ifdef KERNEL
  26 #include "param.h"
  27 #else
  28 #include <sys/param.h>
  29 #ifdef  AFS_HPUX_ENV
  30 #include <sys/fs.h>
  31 #endif
  32 #endif
  33
  34 /*
  35  * Bit patterns for identifying fragments in the block map
  36  * used as ((map & around) == inside)
  37  */
  38 int around[9] = {
  39         0x3, 0x7, 0xf, 0x1f, 0x3f, 0x7f, 0xff, 0x1ff, 0x3ff
  40 };
  41 int inside[9] = {
  42         0x0, 0x2, 0x6, 0xe, 0x1e, 0x3e, 0x7e, 0xfe, 0x1fe
  43 };
  44
  45 /*
  46  * Given a block map bit pattern, the frag tables tell whether a
  47  * particular size fragment is available.
  48  *
  49  * used as:
  50  * if ((1 << (size - 1)) & fragtbl[fs->fs_frag][map] {
  51  *      at least one fragment of the indicated size is available
  52  * }
  53  *
  54  * These tables are used by the scanc instruction on the VAX to
  55  * quickly find an appropriate fragment.
  56  */
  57 u_char fragtbl124[256] = {
  58         0x00, 0x16, 0x16, 0x2a, 0x16, 0x16, 0x26, 0x4e,
  59         0x16, 0x16, 0x16, 0x3e, 0x2a, 0x3e, 0x4e, 0x8a,
  60         0x16, 0x16, 0x16, 0x3e, 0x16, 0x16, 0x36, 0x5e,
  61         0x16, 0x16, 0x16, 0x3e, 0x3e, 0x3e, 0x5e, 0x9e,
  62         0x16, 0x16, 0x16, 0x3e, 0x16, 0x16, 0x36, 0x5e,
  63         0x16, 0x16, 0x16, 0x3e, 0x3e, 0x3e, 0x5e, 0x9e,
  64         0x2a, 0x3e, 0x3e, 0x2a, 0x3e, 0x3e, 0x2e, 0x6e,
  65         0x3e, 0x3e, 0x3e, 0x3e, 0x2a, 0x3e, 0x6e, 0xaa,
  66         0x16, 0x16, 0x16, 0x3e, 0x16, 0x16, 0x36, 0x5e,
  67         0x16, 0x16, 0x16, 0x3e, 0x3e, 0x3e, 0x5e, 0x9e,
  68         0x16, 0x16, 0x16, 0x3e, 0x16, 0x16, 0x36, 0x5e,
  69         0x16, 0x16, 0x16, 0x3e, 0x3e, 0x3e, 0x5e, 0x9e,
  70         0x26, 0x36, 0x36, 0x2e, 0x36, 0x36, 0x26, 0x6e,
  71         0x36, 0x36, 0x36, 0x3e, 0x2e, 0x3e, 0x6e, 0xae,
  72         0x4e, 0x5e, 0x5e, 0x6e, 0x5e, 0x5e, 0x6e, 0x4e,
  73         0x5e, 0x5e, 0x5e, 0x7e, 0x6e, 0x7e, 0x4e, 0xce,
  74         0x16, 0x16, 0x16, 0x3e, 0x16, 0x16, 0x36, 0x5e,
  75         0x16, 0x16, 0x16, 0x3e, 0x3e, 0x3e, 0x5e, 0x9e,
  76         0x16, 0x16, 0x16, 0x3e, 0x16, 0x16, 0x36, 0x5e,
  77         0x16, 0x16, 0x16, 0x3e, 0x3e, 0x3e, 0x5e, 0x9e,
  78         0x16, 0x16, 0x16, 0x3e, 0x16, 0x16, 0x36, 0x5e,
  79         0x16, 0x16, 0x16, 0x3e, 0x3e, 0x3e, 0x5e, 0x9e,
  80         0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x7e,
  81         0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x7e, 0xbe,
  82         0x2a, 0x3e, 0x3e, 0x2a, 0x3e, 0x3e, 0x2e, 0x6e,
  83         0x3e, 0x3e, 0x3e, 0x3e, 0x2a, 0x3e, 0x6e, 0xaa,
  84         0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x7e,
  85         0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x7e, 0xbe,
  86         0x4e, 0x5e, 0x5e, 0x6e, 0x5e, 0x5e, 0x6e, 0x4e,
  87         0x5e, 0x5e, 0x5e, 0x7e, 0x6e, 0x7e, 0x4e, 0xce,
  88         0x8a, 0x9e, 0x9e, 0xaa, 0x9e, 0x9e, 0xae, 0xce,
  89         0x9e, 0x9e, 0x9e, 0xbe, 0xaa, 0xbe, 0xce, 0x8a,
  90 };
  91
  92 u_char fragtbl8[256] = {
  93         0x00, 0x01, 0x01, 0x02, 0x01, 0x01, 0x02, 0x04,
  94         0x01, 0x01, 0x01, 0x03, 0x02, 0x03, 0x04, 0x08,
  95         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05,
  96         0x02, 0x03, 0x03, 0x02, 0x04, 0x05, 0x08, 0x10,
  97         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05,
  98         0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
  99         0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06,
 100         0x04, 0x05, 0x05, 0x06, 0x08, 0x09, 0x10, 0x20,
 101         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05,
 102         0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
 103         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05,
 104         0x03, 0x03, 0x03, 0x03, 0x05, 0x05, 0x09, 0x11,
 105         0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06,
 106         0x03, 0x03, 0x03, 0x03, 0x02, 0x03, 0x06, 0x0a,
 107         0x04, 0x05, 0x05, 0x06, 0x05, 0x05, 0x06, 0x04,
 108         0x08, 0x09, 0x09, 0x0a, 0x10, 0x11, 0x20, 0x40,
 109         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05,
 110         0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
 111         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05,
 112         0x03, 0x03, 0x03, 0x03, 0x05, 0x05, 0x09, 0x11,
 113         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05,
 114         0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
 115         0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x07,
 116         0x05, 0x05, 0x05, 0x07, 0x09, 0x09, 0x11, 0x21,
 117         0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06,
 118         0x03, 0x03, 0x03, 0x03, 0x02, 0x03, 0x06, 0x0a,
 119         0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x07,
 120         0x02, 0x03, 0x03, 0x02, 0x06, 0x07, 0x0a, 0x12,
 121         0x04, 0x05, 0x05, 0x06, 0x05, 0x05, 0x06, 0x04,
 122         0x05, 0x05, 0x05, 0x07, 0x06, 0x07, 0x04, 0x0c,
 123         0x08, 0x09, 0x09, 0x0a, 0x09, 0x09, 0x0a, 0x0c,
 124         0x10, 0x11, 0x11, 0x12, 0x20, 0x21, 0x40, 0x80,
 125 };
 126
 127 /*
 128  * The actual fragtbl array.
 129  */
 130 u_char *fragtbl[MAXFRAG + 1] = {
 131         0, fragtbl124, fragtbl124, 0, fragtbl124, 0, 0, 0, fragtbl8,
 132 };