1139825Simp/*- 21541Srgrimes * Copyright (c) 1982, 1986, 1993 31541Srgrimes * The Regents of the University of California. All rights reserved. 41541Srgrimes * 51541Srgrimes * Redistribution and use in source and binary forms, with or without 61541Srgrimes * modification, are permitted provided that the following conditions 71541Srgrimes * are met: 81541Srgrimes * 1. Redistributions of source code must retain the above copyright 91541Srgrimes * notice, this list of conditions and the following disclaimer. 101541Srgrimes * 2. Redistributions in binary form must reproduce the above copyright 111541Srgrimes * notice, this list of conditions and the following disclaimer in the 121541Srgrimes * documentation and/or other materials provided with the distribution. 131541Srgrimes * 4. Neither the name of the University nor the names of its contributors 141541Srgrimes * may be used to endorse or promote products derived from this software 151541Srgrimes * without specific prior written permission. 161541Srgrimes * 171541Srgrimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 181541Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 191541Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 201541Srgrimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 211541Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 221541Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 231541Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 241541Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 251541Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 261541Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 271541Srgrimes * SUCH DAMAGE. 281541Srgrimes * 291541Srgrimes * @(#)ffs_tables.c 8.1 (Berkeley) 6/11/93 301541Srgrimes */ 311541Srgrimes 32116192Sobrien#include <sys/cdefs.h> 33116192Sobrien__FBSDID("$FreeBSD$"); 34116192Sobrien 351541Srgrimes#include <sys/param.h> 3698542Smckusick#include <ufs/ufs/dinode.h> 3793736Sphk#include <ufs/ffs/fs.h> 381541Srgrimes 391541Srgrimes/* 401541Srgrimes * Bit patterns for identifying fragments in the block map 411541Srgrimes * used as ((map & around) == inside) 421541Srgrimes */ 431541Srgrimesint around[9] = { 441541Srgrimes 0x3, 0x7, 0xf, 0x1f, 0x3f, 0x7f, 0xff, 0x1ff, 0x3ff 451541Srgrimes}; 461541Srgrimesint inside[9] = { 471541Srgrimes 0x0, 0x2, 0x6, 0xe, 0x1e, 0x3e, 0x7e, 0xfe, 0x1fe 481541Srgrimes}; 491541Srgrimes 501541Srgrimes/* 511541Srgrimes * Given a block map bit pattern, the frag tables tell whether a 528876Srgrimes * particular size fragment is available. 531541Srgrimes * 541541Srgrimes * used as: 551541Srgrimes * if ((1 << (size - 1)) & fragtbl[fs->fs_frag][map] { 561541Srgrimes * at least one fragment of the indicated size is available 571541Srgrimes * } 581541Srgrimes * 591541Srgrimes * These tables are used by the scanc instruction on the VAX to 601541Srgrimes * quickly find an appropriate fragment. 611541Srgrimes */ 6212911Sphkstatic u_char fragtbl124[256] = { 631541Srgrimes 0x00, 0x16, 0x16, 0x2a, 0x16, 0x16, 0x26, 0x4e, 641541Srgrimes 0x16, 0x16, 0x16, 0x3e, 0x2a, 0x3e, 0x4e, 0x8a, 651541Srgrimes 0x16, 0x16, 0x16, 0x3e, 0x16, 0x16, 0x36, 0x5e, 661541Srgrimes 0x16, 0x16, 0x16, 0x3e, 0x3e, 0x3e, 0x5e, 0x9e, 671541Srgrimes 0x16, 0x16, 0x16, 0x3e, 0x16, 0x16, 0x36, 0x5e, 681541Srgrimes 0x16, 0x16, 0x16, 0x3e, 0x3e, 0x3e, 0x5e, 0x9e, 691541Srgrimes 0x2a, 0x3e, 0x3e, 0x2a, 0x3e, 0x3e, 0x2e, 0x6e, 701541Srgrimes 0x3e, 0x3e, 0x3e, 0x3e, 0x2a, 0x3e, 0x6e, 0xaa, 711541Srgrimes 0x16, 0x16, 0x16, 0x3e, 0x16, 0x16, 0x36, 0x5e, 721541Srgrimes 0x16, 0x16, 0x16, 0x3e, 0x3e, 0x3e, 0x5e, 0x9e, 731541Srgrimes 0x16, 0x16, 0x16, 0x3e, 0x16, 0x16, 0x36, 0x5e, 741541Srgrimes 0x16, 0x16, 0x16, 0x3e, 0x3e, 0x3e, 0x5e, 0x9e, 751541Srgrimes 0x26, 0x36, 0x36, 0x2e, 0x36, 0x36, 0x26, 0x6e, 761541Srgrimes 0x36, 0x36, 0x36, 0x3e, 0x2e, 0x3e, 0x6e, 0xae, 771541Srgrimes 0x4e, 0x5e, 0x5e, 0x6e, 0x5e, 0x5e, 0x6e, 0x4e, 781541Srgrimes 0x5e, 0x5e, 0x5e, 0x7e, 0x6e, 0x7e, 0x4e, 0xce, 791541Srgrimes 0x16, 0x16, 0x16, 0x3e, 0x16, 0x16, 0x36, 0x5e, 801541Srgrimes 0x16, 0x16, 0x16, 0x3e, 0x3e, 0x3e, 0x5e, 0x9e, 811541Srgrimes 0x16, 0x16, 0x16, 0x3e, 0x16, 0x16, 0x36, 0x5e, 821541Srgrimes 0x16, 0x16, 0x16, 0x3e, 0x3e, 0x3e, 0x5e, 0x9e, 831541Srgrimes 0x16, 0x16, 0x16, 0x3e, 0x16, 0x16, 0x36, 0x5e, 841541Srgrimes 0x16, 0x16, 0x16, 0x3e, 0x3e, 0x3e, 0x5e, 0x9e, 851541Srgrimes 0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x7e, 861541Srgrimes 0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x7e, 0xbe, 871541Srgrimes 0x2a, 0x3e, 0x3e, 0x2a, 0x3e, 0x3e, 0x2e, 0x6e, 881541Srgrimes 0x3e, 0x3e, 0x3e, 0x3e, 0x2a, 0x3e, 0x6e, 0xaa, 891541Srgrimes 0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x7e, 901541Srgrimes 0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x7e, 0xbe, 911541Srgrimes 0x4e, 0x5e, 0x5e, 0x6e, 0x5e, 0x5e, 0x6e, 0x4e, 921541Srgrimes 0x5e, 0x5e, 0x5e, 0x7e, 0x6e, 0x7e, 0x4e, 0xce, 931541Srgrimes 0x8a, 0x9e, 0x9e, 0xaa, 0x9e, 0x9e, 0xae, 0xce, 941541Srgrimes 0x9e, 0x9e, 0x9e, 0xbe, 0xaa, 0xbe, 0xce, 0x8a, 951541Srgrimes}; 961541Srgrimes 9712911Sphkstatic u_char fragtbl8[256] = { 981541Srgrimes 0x00, 0x01, 0x01, 0x02, 0x01, 0x01, 0x02, 0x04, 991541Srgrimes 0x01, 0x01, 0x01, 0x03, 0x02, 0x03, 0x04, 0x08, 1001541Srgrimes 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 1011541Srgrimes 0x02, 0x03, 0x03, 0x02, 0x04, 0x05, 0x08, 0x10, 1021541Srgrimes 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 1031541Srgrimes 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09, 1041541Srgrimes 0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 1051541Srgrimes 0x04, 0x05, 0x05, 0x06, 0x08, 0x09, 0x10, 0x20, 1061541Srgrimes 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 1071541Srgrimes 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09, 1081541Srgrimes 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 1091541Srgrimes 0x03, 0x03, 0x03, 0x03, 0x05, 0x05, 0x09, 0x11, 1101541Srgrimes 0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 1111541Srgrimes 0x03, 0x03, 0x03, 0x03, 0x02, 0x03, 0x06, 0x0a, 1121541Srgrimes 0x04, 0x05, 0x05, 0x06, 0x05, 0x05, 0x06, 0x04, 1131541Srgrimes 0x08, 0x09, 0x09, 0x0a, 0x10, 0x11, 0x20, 0x40, 1141541Srgrimes 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 1151541Srgrimes 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09, 1161541Srgrimes 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 1171541Srgrimes 0x03, 0x03, 0x03, 0x03, 0x05, 0x05, 0x09, 0x11, 1181541Srgrimes 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 1191541Srgrimes 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09, 1201541Srgrimes 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x07, 1211541Srgrimes 0x05, 0x05, 0x05, 0x07, 0x09, 0x09, 0x11, 0x21, 1221541Srgrimes 0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 1231541Srgrimes 0x03, 0x03, 0x03, 0x03, 0x02, 0x03, 0x06, 0x0a, 1241541Srgrimes 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x07, 1251541Srgrimes 0x02, 0x03, 0x03, 0x02, 0x06, 0x07, 0x0a, 0x12, 1261541Srgrimes 0x04, 0x05, 0x05, 0x06, 0x05, 0x05, 0x06, 0x04, 1271541Srgrimes 0x05, 0x05, 0x05, 0x07, 0x06, 0x07, 0x04, 0x0c, 1281541Srgrimes 0x08, 0x09, 0x09, 0x0a, 0x09, 0x09, 0x0a, 0x0c, 1291541Srgrimes 0x10, 0x11, 0x11, 0x12, 0x20, 0x21, 0x40, 0x80, 1301541Srgrimes}; 1311541Srgrimes 1321541Srgrimes/* 1331541Srgrimes * The actual fragtbl array. 1341541Srgrimes */ 1351541Srgrimesu_char *fragtbl[MAXFRAG + 1] = { 1361541Srgrimes 0, fragtbl124, fragtbl124, 0, fragtbl124, 0, 0, 0, fragtbl8, 1371541Srgrimes}; 138