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