bsd/ufs/ffs/ffs_tables.c

   1 /*
   2  * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
   3  *
   4  * @APPLE_LICENSE_HEADER_START@
   5  *
   6  * This file contains Original Code and/or Modifications of Original Code
   7  * as defined in and that are subject to the Apple Public Source License
   8  * Version 2.0 (the 'License'). You may not use this file except in
   9  * compliance with the License. Please obtain a copy of the License at
  10  * http://www.opensource.apple.com/apsl/ and read it before using this
  11  * file.
  12  *
  13  * The Original Code and all software distributed under the License are
  14  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  15  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  16  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  18  * Please see the License for the specific language governing rights and
  19  * limitations under the License.
  20  *
  21  * @APPLE_LICENSE_HEADER_END@
  22  */
  23 /* Copyright (c) 1995 NeXT Computer, Inc. All Rights Reserved */
  24 /*
  25  * Copyright (c) 1982, 1986, 1993
  26  *      The Regents of the University of California.  All rights reserved.
  27  *
  28  * Redistribution and use in source and binary forms, with or without
  29  * modification, are permitted provided that the following conditions
  30  * are met:
  31  * 1. Redistributions of source code must retain the above copyright
  32  *    notice, this list of conditions and the following disclaimer.
  33  * 2. Redistributions in binary form must reproduce the above copyright
  34  *    notice, this list of conditions and the following disclaimer in the
  35  *    documentation and/or other materials provided with the distribution.
  36  * 3. All advertising materials mentioning features or use of this software
  37  *    must display the following acknowledgement:
  38  *      This product includes software developed by the University of
  39  *      California, Berkeley and its contributors.
  40  * 4. Neither the name of the University nor the names of its contributors
  41  *    may be used to endorse or promote products derived from this software
  42  *    without specific prior written permission.
  43  *
  44  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  45  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  46  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  47  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  48  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  49  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  50  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  51  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  52  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  53  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  54  * SUCH DAMAGE.
  55  *
  56  *      @(#)ffs_tables.c        8.1 (Berkeley) 6/11/93
  57  */
  58
  59 #include <sys/param.h>
  60
  61 /*
  62  * Bit patterns for identifying fragments in the block map
  63  * used as ((map & around) == inside)
  64  */
  65 int around[9] = {
  66         0x3, 0x7, 0xf, 0x1f, 0x3f, 0x7f, 0xff, 0x1ff, 0x3ff
  67 };
  68 int inside[9] = {
  69         0x0, 0x2, 0x6, 0xe, 0x1e, 0x3e, 0x7e, 0xfe, 0x1fe
  70 };
  71
  72 /*
  73  * Given a block map bit pattern, the frag tables tell whether a
  74  * particular size fragment is available.
  75  *
  76  * used as:
  77  * if ((1 << (size - 1)) & fragtbl[fs->fs_frag][map] {
  78  *      at least one fragment of the indicated size is available
  79  * }
  80  *
  81  * These tables are used by the scanc instruction on the VAX to
  82  * quickly find an appropriate fragment.
  83  */
  84 u_char fragtbl124[256] = {
  85         0x00, 0x16, 0x16, 0x2a, 0x16, 0x16, 0x26, 0x4e,
  86         0x16, 0x16, 0x16, 0x3e, 0x2a, 0x3e, 0x4e, 0x8a,
  87         0x16, 0x16, 0x16, 0x3e, 0x16, 0x16, 0x36, 0x5e,
  88         0x16, 0x16, 0x16, 0x3e, 0x3e, 0x3e, 0x5e, 0x9e,
  89         0x16, 0x16, 0x16, 0x3e, 0x16, 0x16, 0x36, 0x5e,
  90         0x16, 0x16, 0x16, 0x3e, 0x3e, 0x3e, 0x5e, 0x9e,
  91         0x2a, 0x3e, 0x3e, 0x2a, 0x3e, 0x3e, 0x2e, 0x6e,
  92         0x3e, 0x3e, 0x3e, 0x3e, 0x2a, 0x3e, 0x6e, 0xaa,
  93         0x16, 0x16, 0x16, 0x3e, 0x16, 0x16, 0x36, 0x5e,
  94         0x16, 0x16, 0x16, 0x3e, 0x3e, 0x3e, 0x5e, 0x9e,
  95         0x16, 0x16, 0x16, 0x3e, 0x16, 0x16, 0x36, 0x5e,
  96         0x16, 0x16, 0x16, 0x3e, 0x3e, 0x3e, 0x5e, 0x9e,
  97         0x26, 0x36, 0x36, 0x2e, 0x36, 0x36, 0x26, 0x6e,
  98         0x36, 0x36, 0x36, 0x3e, 0x2e, 0x3e, 0x6e, 0xae,
  99         0x4e, 0x5e, 0x5e, 0x6e, 0x5e, 0x5e, 0x6e, 0x4e,
 100         0x5e, 0x5e, 0x5e, 0x7e, 0x6e, 0x7e, 0x4e, 0xce,
 101         0x16, 0x16, 0x16, 0x3e, 0x16, 0x16, 0x36, 0x5e,
 102         0x16, 0x16, 0x16, 0x3e, 0x3e, 0x3e, 0x5e, 0x9e,
 103         0x16, 0x16, 0x16, 0x3e, 0x16, 0x16, 0x36, 0x5e,
 104         0x16, 0x16, 0x16, 0x3e, 0x3e, 0x3e, 0x5e, 0x9e,
 105         0x16, 0x16, 0x16, 0x3e, 0x16, 0x16, 0x36, 0x5e,
 106         0x16, 0x16, 0x16, 0x3e, 0x3e, 0x3e, 0x5e, 0x9e,
 107         0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x7e,
 108         0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x7e, 0xbe,
 109         0x2a, 0x3e, 0x3e, 0x2a, 0x3e, 0x3e, 0x2e, 0x6e,
 110         0x3e, 0x3e, 0x3e, 0x3e, 0x2a, 0x3e, 0x6e, 0xaa,
 111         0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x7e,
 112         0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x7e, 0xbe,
 113         0x4e, 0x5e, 0x5e, 0x6e, 0x5e, 0x5e, 0x6e, 0x4e,
 114         0x5e, 0x5e, 0x5e, 0x7e, 0x6e, 0x7e, 0x4e, 0xce,
 115         0x8a, 0x9e, 0x9e, 0xaa, 0x9e, 0x9e, 0xae, 0xce,
 116         0x9e, 0x9e, 0x9e, 0xbe, 0xaa, 0xbe, 0xce, 0x8a,
 117 };
 118
 119 u_char fragtbl8[256] = {
 120         0x00, 0x01, 0x01, 0x02, 0x01, 0x01, 0x02, 0x04,
 121         0x01, 0x01, 0x01, 0x03, 0x02, 0x03, 0x04, 0x08,
 122         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05,
 123         0x02, 0x03, 0x03, 0x02, 0x04, 0x05, 0x08, 0x10,
 124         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05,
 125         0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
 126         0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06,
 127         0x04, 0x05, 0x05, 0x06, 0x08, 0x09, 0x10, 0x20,
 128         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05,
 129         0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
 130         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05,
 131         0x03, 0x03, 0x03, 0x03, 0x05, 0x05, 0x09, 0x11,
 132         0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06,
 133         0x03, 0x03, 0x03, 0x03, 0x02, 0x03, 0x06, 0x0a,
 134         0x04, 0x05, 0x05, 0x06, 0x05, 0x05, 0x06, 0x04,
 135         0x08, 0x09, 0x09, 0x0a, 0x10, 0x11, 0x20, 0x40,
 136         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05,
 137         0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
 138         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05,
 139         0x03, 0x03, 0x03, 0x03, 0x05, 0x05, 0x09, 0x11,
 140         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05,
 141         0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
 142         0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x07,
 143         0x05, 0x05, 0x05, 0x07, 0x09, 0x09, 0x11, 0x21,
 144         0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06,
 145         0x03, 0x03, 0x03, 0x03, 0x02, 0x03, 0x06, 0x0a,
 146         0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x07,
 147         0x02, 0x03, 0x03, 0x02, 0x06, 0x07, 0x0a, 0x12,
 148         0x04, 0x05, 0x05, 0x06, 0x05, 0x05, 0x06, 0x04,
 149         0x05, 0x05, 0x05, 0x07, 0x06, 0x07, 0x04, 0x0c,
 150         0x08, 0x09, 0x09, 0x0a, 0x09, 0x09, 0x0a, 0x0c,
 151         0x10, 0x11, 0x11, 0x12, 0x20, 0x21, 0x40, 0x80,
 152 };
 153
 154 /*
 155  * The actual fragtbl array.
 156  */
 157 u_char *fragtbl[MAXFRAG + 1] = {
 158         0, fragtbl124, fragtbl124, 0, fragtbl124, 0, 0, 0, fragtbl8,
 159 };