bsd/ufs/ffs/ffs_tables.c

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