[unix-history] / usr / src / sys / ufs / ffs / ffs_tables.c

/*
 * Copyright (c) 1982, 1986 Regents of the University of California.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms are permitted
 * provided that the above copyright notice and this paragraph are
 * duplicated in all such forms and that any documentation,
 * advertising materials, and other materials related to such
 * distribution and use acknowledge that the software was developed
 * by the University of California, Berkeley.  The name of the
 * University may not be used to endorse or promote products derived
 * from this software without specific prior written permission.
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
 *
 *	@(#)ffs_tables.c	7.3 (Berkeley) %G%
 */

#ifdef KERNEL
#include "param.h"
#else
#include <sys/param.h>
#endif

/*
 * Bit patterns for identifying fragments in the block map
 * used as ((map & around) == inside)
 */
int around[9] = {
	0x3, 0x7, 0xf, 0x1f, 0x3f, 0x7f, 0xff, 0x1ff, 0x3ff
};
int inside[9] = {
	0x0, 0x2, 0x6, 0xe, 0x1e, 0x3e, 0x7e, 0xfe, 0x1fe
};

/*
 * Given a block map bit pattern, the frag tables tell whether a
 * particular size fragment is available. 
 *
 * used as:
 * if ((1 << (size - 1)) & fragtbl[fs->fs_frag][map] {
 *	at least one fragment of the indicated size is available
 * }
 *
 * These tables are used by the scanc instruction on the VAX to
 * quickly find an appropriate fragment.
 */
u_char fragtbl124[256] = {
	0x00, 0x16, 0x16, 0x2a, 0x16, 0x16, 0x26, 0x4e,
	0x16, 0x16, 0x16, 0x3e, 0x2a, 0x3e, 0x4e, 0x8a,
	0x16, 0x16, 0x16, 0x3e, 0x16, 0x16, 0x36, 0x5e,
	0x16, 0x16, 0x16, 0x3e, 0x3e, 0x3e, 0x5e, 0x9e,
	0x16, 0x16, 0x16, 0x3e, 0x16, 0x16, 0x36, 0x5e,
	0x16, 0x16, 0x16, 0x3e, 0x3e, 0x3e, 0x5e, 0x9e,
	0x2a, 0x3e, 0x3e, 0x2a, 0x3e, 0x3e, 0x2e, 0x6e,
	0x3e, 0x3e, 0x3e, 0x3e, 0x2a, 0x3e, 0x6e, 0xaa,
	0x16, 0x16, 0x16, 0x3e, 0x16, 0x16, 0x36, 0x5e,
	0x16, 0x16, 0x16, 0x3e, 0x3e, 0x3e, 0x5e, 0x9e,
	0x16, 0x16, 0x16, 0x3e, 0x16, 0x16, 0x36, 0x5e,
	0x16, 0x16, 0x16, 0x3e, 0x3e, 0x3e, 0x5e, 0x9e,
	0x26, 0x36, 0x36, 0x2e, 0x36, 0x36, 0x26, 0x6e,
	0x36, 0x36, 0x36, 0x3e, 0x2e, 0x3e, 0x6e, 0xae,
	0x4e, 0x5e, 0x5e, 0x6e, 0x5e, 0x5e, 0x6e, 0x4e,
	0x5e, 0x5e, 0x5e, 0x7e, 0x6e, 0x7e, 0x4e, 0xce,
	0x16, 0x16, 0x16, 0x3e, 0x16, 0x16, 0x36, 0x5e,
	0x16, 0x16, 0x16, 0x3e, 0x3e, 0x3e, 0x5e, 0x9e,
	0x16, 0x16, 0x16, 0x3e, 0x16, 0x16, 0x36, 0x5e,
	0x16, 0x16, 0x16, 0x3e, 0x3e, 0x3e, 0x5e, 0x9e,
	0x16, 0x16, 0x16, 0x3e, 0x16, 0x16, 0x36, 0x5e,
	0x16, 0x16, 0x16, 0x3e, 0x3e, 0x3e, 0x5e, 0x9e,
	0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x7e,
	0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x7e, 0xbe,
	0x2a, 0x3e, 0x3e, 0x2a, 0x3e, 0x3e, 0x2e, 0x6e,
	0x3e, 0x3e, 0x3e, 0x3e, 0x2a, 0x3e, 0x6e, 0xaa,
	0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x7e,
	0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x7e, 0xbe,
	0x4e, 0x5e, 0x5e, 0x6e, 0x5e, 0x5e, 0x6e, 0x4e,
	0x5e, 0x5e, 0x5e, 0x7e, 0x6e, 0x7e, 0x4e, 0xce,
	0x8a, 0x9e, 0x9e, 0xaa, 0x9e, 0x9e, 0xae, 0xce,
	0x9e, 0x9e, 0x9e, 0xbe, 0xaa, 0xbe, 0xce, 0x8a,
};

u_char fragtbl8[256] = {
	0x00, 0x01, 0x01, 0x02, 0x01, 0x01, 0x02, 0x04,
	0x01, 0x01, 0x01, 0x03, 0x02, 0x03, 0x04, 0x08,
	0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05,
	0x02, 0x03, 0x03, 0x02, 0x04, 0x05, 0x08, 0x10,
	0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05,
	0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
	0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06,
	0x04, 0x05, 0x05, 0x06, 0x08, 0x09, 0x10, 0x20,
	0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05,
	0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
	0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05,
	0x03, 0x03, 0x03, 0x03, 0x05, 0x05, 0x09, 0x11,
	0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06,
	0x03, 0x03, 0x03, 0x03, 0x02, 0x03, 0x06, 0x0a,
	0x04, 0x05, 0x05, 0x06, 0x05, 0x05, 0x06, 0x04,
	0x08, 0x09, 0x09, 0x0a, 0x10, 0x11, 0x20, 0x40,
	0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05,
	0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
	0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05,
	0x03, 0x03, 0x03, 0x03, 0x05, 0x05, 0x09, 0x11,
	0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05,
	0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
	0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x07,
	0x05, 0x05, 0x05, 0x07, 0x09, 0x09, 0x11, 0x21,
	0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06,
	0x03, 0x03, 0x03, 0x03, 0x02, 0x03, 0x06, 0x0a,
	0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x07,
	0x02, 0x03, 0x03, 0x02, 0x06, 0x07, 0x0a, 0x12,
	0x04, 0x05, 0x05, 0x06, 0x05, 0x05, 0x06, 0x04,
	0x05, 0x05, 0x05, 0x07, 0x06, 0x07, 0x04, 0x0c,
	0x08, 0x09, 0x09, 0x0a, 0x09, 0x09, 0x0a, 0x0c,
	0x10, 0x11, 0x11, 0x12, 0x20, 0x21, 0x40, 0x80,
};

/*
 * The actual fragtbl array.
 */
u_char *fragtbl[MAXFRAG + 1] = {
	0, fragtbl124, fragtbl124, 0, fragtbl124, 0, 0, 0, fragtbl8,
};
Commit	Line	Data
da7c5cc6	1	/*
0880b18e	2	* Copyright (c) 1982, 1986 Regents of the University of California.
4aa5c983	3	* All rights reserved.
da7c5cc6	4	*
4aa5c983 KM	5	* Redistribution and use in source and binary forms are permitted
	6	* provided that the above copyright notice and this paragraph are
	7	* duplicated in all such forms and that any documentation,
	8	* advertising materials, and other materials related to such
	9	* distribution and use acknowledge that the software was developed
	10	* by the University of California, Berkeley. The name of the
	11	* University may not be used to endorse or promote products derived
	12	* from this software without specific prior written permission.
	13	* THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
	14	* IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
	15	* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
	16	*
	17	* @(#)ffs_tables.c 7.3 (Berkeley) %G%
da7c5cc6	18	*/
5576d804	19
10deb49e	20	#ifdef KERNEL
94368568	21	#include "param.h"
10deb49e KB	22	#else
	23	#include <sys/param.h>
	24	#endif
5576d804	25
5576d804	26	/*
88a7a62a	27	* Bit patterns for identifying fragments in the block map
5576d804 KM	28	* used as ((map & around) == inside)
	29	*/
	30	int around[9] = {
	31	0x3, 0x7, 0xf, 0x1f, 0x3f, 0x7f, 0xff, 0x1ff, 0x3ff
	32	};
	33	int inside[9] = {
	34	0x0, 0x2, 0x6, 0xe, 0x1e, 0x3e, 0x7e, 0xfe, 0x1fe
	35	};
	36
	37	/*
88a7a62a	38	* Given a block map bit pattern, the frag tables tell whether a
5576d804	39	* particular size fragment is available.
b6407c9d	40	*
5576d804	41	* used as:
b6407c9d	42	* if ((1 << (size - 1)) & fragtbl[fs->fs_frag][map] {
5576d804 KM	43	* at least one fragment of the indicated size is available
5576d804 KM	44	* }
b6407c9d KM	45	*
b6407c9d KM	46	* These tables are used by the scanc instruction on the VAX to
5576d804 KM	47	* quickly find an appropriate fragment.
5576d804 KM	48	*/
88a7a62a	49	u_char fragtbl124[256] = {
156b8f82 KM	50	0x00, 0x16, 0x16, 0x2a, 0x16, 0x16, 0x26, 0x4e,
	51	0x16, 0x16, 0x16, 0x3e, 0x2a, 0x3e, 0x4e, 0x8a,
	52	0x16, 0x16, 0x16, 0x3e, 0x16, 0x16, 0x36, 0x5e,
	53	0x16, 0x16, 0x16, 0x3e, 0x3e, 0x3e, 0x5e, 0x9e,
	54	0x16, 0x16, 0x16, 0x3e, 0x16, 0x16, 0x36, 0x5e,
	55	0x16, 0x16, 0x16, 0x3e, 0x3e, 0x3e, 0x5e, 0x9e,
	56	0x2a, 0x3e, 0x3e, 0x2a, 0x3e, 0x3e, 0x2e, 0x6e,
	57	0x3e, 0x3e, 0x3e, 0x3e, 0x2a, 0x3e, 0x6e, 0xaa,
	58	0x16, 0x16, 0x16, 0x3e, 0x16, 0x16, 0x36, 0x5e,
	59	0x16, 0x16, 0x16, 0x3e, 0x3e, 0x3e, 0x5e, 0x9e,
	60	0x16, 0x16, 0x16, 0x3e, 0x16, 0x16, 0x36, 0x5e,
	61	0x16, 0x16, 0x16, 0x3e, 0x3e, 0x3e, 0x5e, 0x9e,
	62	0x26, 0x36, 0x36, 0x2e, 0x36, 0x36, 0x26, 0x6e,
	63	0x36, 0x36, 0x36, 0x3e, 0x2e, 0x3e, 0x6e, 0xae,
	64	0x4e, 0x5e, 0x5e, 0x6e, 0x5e, 0x5e, 0x6e, 0x4e,
	65	0x5e, 0x5e, 0x5e, 0x7e, 0x6e, 0x7e, 0x4e, 0xce,
	66	0x16, 0x16, 0x16, 0x3e, 0x16, 0x16, 0x36, 0x5e,
	67	0x16, 0x16, 0x16, 0x3e, 0x3e, 0x3e, 0x5e, 0x9e,
	68	0x16, 0x16, 0x16, 0x3e, 0x16, 0x16, 0x36, 0x5e,
	69	0x16, 0x16, 0x16, 0x3e, 0x3e, 0x3e, 0x5e, 0x9e,
	70	0x16, 0x16, 0x16, 0x3e, 0x16, 0x16, 0x36, 0x5e,
	71	0x16, 0x16, 0x16, 0x3e, 0x3e, 0x3e, 0x5e, 0x9e,
	72	0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x7e,
	73	0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x7e, 0xbe,
	74	0x2a, 0x3e, 0x3e, 0x2a, 0x3e, 0x3e, 0x2e, 0x6e,
	75	0x3e, 0x3e, 0x3e, 0x3e, 0x2a, 0x3e, 0x6e, 0xaa,
	76	0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x7e,
	77	0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x7e, 0xbe,
	78	0x4e, 0x5e, 0x5e, 0x6e, 0x5e, 0x5e, 0x6e, 0x4e,
	79	0x5e, 0x5e, 0x5e, 0x7e, 0x6e, 0x7e, 0x4e, 0xce,
	80	0x8a, 0x9e, 0x9e, 0xaa, 0x9e, 0x9e, 0xae, 0xce,
	81	0x9e, 0x9e, 0x9e, 0xbe, 0xaa, 0xbe, 0xce, 0x8a,
5576d804	82	};
5576d804	83
88a7a62a	84	u_char fragtbl8[256] = {
5576d804 KM	85	0x00, 0x01, 0x01, 0x02, 0x01, 0x01, 0x02, 0x04,
	86	0x01, 0x01, 0x01, 0x03, 0x02, 0x03, 0x04, 0x08,
	87	0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05,
	88	0x02, 0x03, 0x03, 0x02, 0x04, 0x05, 0x08, 0x10,
	89	0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05,
	90	0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
	91	0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06,
	92	0x04, 0x05, 0x05, 0x06, 0x08, 0x09, 0x10, 0x20,
	93	0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05,
	94	0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
	95	0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05,
	96	0x03, 0x03, 0x03, 0x03, 0x05, 0x05, 0x09, 0x11,
	97	0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06,
	98	0x03, 0x03, 0x03, 0x03, 0x02, 0x03, 0x06, 0x0a,
	99	0x04, 0x05, 0x05, 0x06, 0x05, 0x05, 0x06, 0x04,
	100	0x08, 0x09, 0x09, 0x0a, 0x10, 0x11, 0x20, 0x40,
	101	0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05,
	102	0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
	103	0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05,
	104	0x03, 0x03, 0x03, 0x03, 0x05, 0x05, 0x09, 0x11,
	105	0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05,
	106	0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
	107	0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x07,
	108	0x05, 0x05, 0x05, 0x07, 0x09, 0x09, 0x11, 0x21,
	109	0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06,
	110	0x03, 0x03, 0x03, 0x03, 0x02, 0x03, 0x06, 0x0a,
	111	0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x07,
	112	0x02, 0x03, 0x03, 0x02, 0x06, 0x07, 0x0a, 0x12,
	113	0x04, 0x05, 0x05, 0x06, 0x05, 0x05, 0x06, 0x04,
	114	0x05, 0x05, 0x05, 0x07, 0x06, 0x07, 0x04, 0x0c,
	115	0x08, 0x09, 0x09, 0x0a, 0x09, 0x09, 0x0a, 0x0c,
	116	0x10, 0x11, 0x11, 0x12, 0x20, 0x21, 0x40, 0x80,
	117	};
b6407c9d KM	118
b6407c9d KM	119	/*
88a7a62a	120	* The actual fragtbl array.
b6407c9d	121	*/
88a7a62a	122	u_char *fragtbl[MAXFRAG + 1] = {
156b8f82	123	0, fragtbl124, fragtbl124, 0, fragtbl124, 0, 0, 0, fragtbl8,
b6407c9d	124	};