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