root/ufs/ffs/ffs_tables.c

    1 /*      $OpenBSD: ffs_tables.c,v 1.5 2003/08/26 16:10:57 mickey Exp $   */
    2 /*      $NetBSD: ffs_tables.c,v 1.2 1994/06/29 06:46:35 cgd Exp $       */
    4 /*
    5  * Copyright (c) 1982, 1986, 1993
    6  *      The Regents of the University of California.  All rights reserved.
    7  *
    8  * Redistribution and use in source and binary forms, with or without
    9  * modification, are permitted provided that the following conditions
   10  * are met:
   11  * 1. Redistributions of source code must retain the above copyright
   12  *    notice, this list of conditions and the following disclaimer.
   13  * 2. Redistributions in binary form must reproduce the above copyright
   14  *    notice, this list of conditions and the following disclaimer in the
   15  *    documentation and/or other materials provided with the distribution.
   16  * 3. Neither the name of the University nor the names of its contributors
   17  *    may be used to endorse or promote products derived from this software
   18  *    without specific prior written permission.
   19  *
   20  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
   21  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
   22  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
   23  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
   24  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
   25  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
   26  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
   27  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
   28  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
   29  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
   30  * SUCH DAMAGE.
   31  *
   32  *      @(#)ffs_tables.c        8.1 (Berkeley) 6/11/93
   33  */
   35 #include <sys/param.h>
   36 #include <ufs/ffs/fs.h>
   38 /*
   39  * Bit patterns for identifying fragments in the block map
   40  * used as ((map & around) == inside)
   41  */
   42 const int around[9] = {
   43         0x3, 0x7, 0xf, 0x1f, 0x3f, 0x7f, 0xff, 0x1ff, 0x3ff
   44 };
   45 const int inside[9] = {
   46         0x0, 0x2, 0x6, 0xe, 0x1e, 0x3e, 0x7e, 0xfe, 0x1fe
   47 };
   49 /*
   50  * Given a block map bit pattern, the frag tables tell whether a
   51  * particular size fragment is available.
   52  *
   53  * used as:
   54  * if ((1 << (size - 1)) & fragtbl[fs->fs_frag][map] {
   55  *      at least one fragment of the indicated size is available
   56  * }
   57  *
   58  * These tables are used by the scanc instruction on the VAX to
   59  * quickly find an appropriate fragment.
   60  */
   61 const u_char fragtbl124[256] = {
   62         0x00, 0x16, 0x16, 0x2a, 0x16, 0x16, 0x26, 0x4e,
   63         0x16, 0x16, 0x16, 0x3e, 0x2a, 0x3e, 0x4e, 0x8a,
   64         0x16, 0x16, 0x16, 0x3e, 0x16, 0x16, 0x36, 0x5e,
   65         0x16, 0x16, 0x16, 0x3e, 0x3e, 0x3e, 0x5e, 0x9e,
   66         0x16, 0x16, 0x16, 0x3e, 0x16, 0x16, 0x36, 0x5e,
   67         0x16, 0x16, 0x16, 0x3e, 0x3e, 0x3e, 0x5e, 0x9e,
   68         0x2a, 0x3e, 0x3e, 0x2a, 0x3e, 0x3e, 0x2e, 0x6e,
   69         0x3e, 0x3e, 0x3e, 0x3e, 0x2a, 0x3e, 0x6e, 0xaa,
   70         0x16, 0x16, 0x16, 0x3e, 0x16, 0x16, 0x36, 0x5e,
   71         0x16, 0x16, 0x16, 0x3e, 0x3e, 0x3e, 0x5e, 0x9e,
   72         0x16, 0x16, 0x16, 0x3e, 0x16, 0x16, 0x36, 0x5e,
   73         0x16, 0x16, 0x16, 0x3e, 0x3e, 0x3e, 0x5e, 0x9e,
   74         0x26, 0x36, 0x36, 0x2e, 0x36, 0x36, 0x26, 0x6e,
   75         0x36, 0x36, 0x36, 0x3e, 0x2e, 0x3e, 0x6e, 0xae,
   76         0x4e, 0x5e, 0x5e, 0x6e, 0x5e, 0x5e, 0x6e, 0x4e,
   77         0x5e, 0x5e, 0x5e, 0x7e, 0x6e, 0x7e, 0x4e, 0xce,
   78         0x16, 0x16, 0x16, 0x3e, 0x16, 0x16, 0x36, 0x5e,
   79         0x16, 0x16, 0x16, 0x3e, 0x3e, 0x3e, 0x5e, 0x9e,
   80         0x16, 0x16, 0x16, 0x3e, 0x16, 0x16, 0x36, 0x5e,
   81         0x16, 0x16, 0x16, 0x3e, 0x3e, 0x3e, 0x5e, 0x9e,
   82         0x16, 0x16, 0x16, 0x3e, 0x16, 0x16, 0x36, 0x5e,
   83         0x16, 0x16, 0x16, 0x3e, 0x3e, 0x3e, 0x5e, 0x9e,
   84         0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x7e,
   85         0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x7e, 0xbe,
   86         0x2a, 0x3e, 0x3e, 0x2a, 0x3e, 0x3e, 0x2e, 0x6e,
   87         0x3e, 0x3e, 0x3e, 0x3e, 0x2a, 0x3e, 0x6e, 0xaa,
   88         0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x7e,
   89         0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x7e, 0xbe,
   90         0x4e, 0x5e, 0x5e, 0x6e, 0x5e, 0x5e, 0x6e, 0x4e,
   91         0x5e, 0x5e, 0x5e, 0x7e, 0x6e, 0x7e, 0x4e, 0xce,
   92         0x8a, 0x9e, 0x9e, 0xaa, 0x9e, 0x9e, 0xae, 0xce,
   93         0x9e, 0x9e, 0x9e, 0xbe, 0xaa, 0xbe, 0xce, 0x8a,
   94 };
   96 const u_char fragtbl8[256] = {
   97         0x00, 0x01, 0x01, 0x02, 0x01, 0x01, 0x02, 0x04,
   98         0x01, 0x01, 0x01, 0x03, 0x02, 0x03, 0x04, 0x08,
   99         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05,
  100         0x02, 0x03, 0x03, 0x02, 0x04, 0x05, 0x08, 0x10,
  101         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05,
  102         0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
  103         0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06,
  104         0x04, 0x05, 0x05, 0x06, 0x08, 0x09, 0x10, 0x20,
  105         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05,
  106         0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
  107         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05,
  108         0x03, 0x03, 0x03, 0x03, 0x05, 0x05, 0x09, 0x11,
  109         0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06,
  110         0x03, 0x03, 0x03, 0x03, 0x02, 0x03, 0x06, 0x0a,
  111         0x04, 0x05, 0x05, 0x06, 0x05, 0x05, 0x06, 0x04,
  112         0x08, 0x09, 0x09, 0x0a, 0x10, 0x11, 0x20, 0x40,
  113         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05,
  114         0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
  115         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05,
  116         0x03, 0x03, 0x03, 0x03, 0x05, 0x05, 0x09, 0x11,
  117         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05,
  118         0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
  119         0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x07,
  120         0x05, 0x05, 0x05, 0x07, 0x09, 0x09, 0x11, 0x21,
  121         0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06,
  122         0x03, 0x03, 0x03, 0x03, 0x02, 0x03, 0x06, 0x0a,
  123         0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x07,
  124         0x02, 0x03, 0x03, 0x02, 0x06, 0x07, 0x0a, 0x12,
  125         0x04, 0x05, 0x05, 0x06, 0x05, 0x05, 0x06, 0x04,
  126         0x05, 0x05, 0x05, 0x07, 0x06, 0x07, 0x04, 0x0c,
  127         0x08, 0x09, 0x09, 0x0a, 0x09, 0x09, 0x0a, 0x0c,
  128         0x10, 0x11, 0x11, 0x12, 0x20, 0x21, 0x40, 0x80,
  129 };
  131 /*
  132  * The actual fragtbl array.
  133  */
  134 const u_char *fragtbl[MAXFRAG + 1] = {
  135         0, fragtbl124, fragtbl124, 0, fragtbl124, 0, 0, 0, fragtbl8,
  136 };