From 156b8f82f30a664dbacfbddc3087f49fd57215bc Mon Sep 17 00:00:00 2001 From: Kirk McKusick Date: Tue, 23 Mar 1982 20:57:12 -0800 Subject: [PATCH] compress frag tables SCCS-vsn: sbin/fsck/main.c 1.28 SCCS-vsn: sbin/icheck/icheck.c 1.21 SCCS-vsn: sys/ufs/ffs/ffs_tables.c 1.4 SCCS-vsn: sys/ufs/ffs/ffs_alloc.c 1.20 SCCS-vsn: sys/ufs/lfs/lfs_alloc.c 1.20 --- usr/src/sbin/fsck/main.c | 4 +- usr/src/sbin/icheck/icheck.c | 4 +- usr/src/sys/ufs/ffs/ffs_alloc.c | 8 +- usr/src/sys/ufs/ffs/ffs_tables.c | 140 ++++++++----------------------- usr/src/sys/ufs/lfs/lfs_alloc.c | 8 +- 5 files changed, 47 insertions(+), 117 deletions(-) diff --git a/usr/src/sbin/fsck/main.c b/usr/src/sbin/fsck/main.c index 380dd9c9d3..9671f9bd27 100644 --- a/usr/src/sbin/fsck/main.c +++ b/usr/src/sbin/fsck/main.c @@ -1,4 +1,4 @@ -static char *sccsid = "@(#)main.c 1.27 (Berkeley) %G%"; +static char *sccsid = "@(#)main.c 1.28 (Berkeley) %G%"; #include #include @@ -1643,7 +1643,7 @@ fragacct(fs, fragmap, fraglist, cnt) inblk = (int)(fragtbl[fs->fs_frag][fragmap] << 1); fragmap <<= 1; for (siz = 1; siz < fs->fs_frag; siz++) { - if (((1 << siz) & inblk) == 0) + if ((inblk & (1 << (siz + (fs->fs_frag % NBBY)))) == 0) continue; field = around[siz]; subfield = inside[siz]; diff --git a/usr/src/sbin/icheck/icheck.c b/usr/src/sbin/icheck/icheck.c index 1e36e98469..9b8a8d009f 100644 --- a/usr/src/sbin/icheck/icheck.c +++ b/usr/src/sbin/icheck/icheck.c @@ -1,4 +1,4 @@ -static char *sccsid = "@(#)icheck.c 1.20 (Berkeley) %G%"; +static char *sccsid = "@(#)icheck.c 1.21 (Berkeley) %G%"; /* * icheck @@ -553,7 +553,7 @@ fragacct(fs, fragmap, fraglist, cnt) inblk = (int)(fragtbl[fs->fs_frag][fragmap] << 1); fragmap <<= 1; for (siz = 1; siz < fs->fs_frag; siz++) { - if (((1 << siz) & inblk) == 0) + if ((inblk & (1 << (siz + (fs->fs_frag % NBBY)))) == 0) continue; field = around[siz]; subfield = inside[siz]; diff --git a/usr/src/sys/ufs/ffs/ffs_alloc.c b/usr/src/sys/ufs/ffs/ffs_alloc.c index d102310809..c50a7f6b9a 100644 --- a/usr/src/sys/ufs/ffs/ffs_alloc.c +++ b/usr/src/sys/ufs/ffs/ffs_alloc.c @@ -1,6 +1,6 @@ /* Copyright (c) 1981 Regents of the University of California */ -static char vers[] = "@(#)ffs_alloc.c 1.19 %G%"; +static char vers[] = "@(#)ffs_alloc.c 1.20 %G%"; /* alloc.c 4.8 81/03/08 */ @@ -788,13 +788,13 @@ mapsearch(fs, cgp, bpref, allocsiz) start = cgp->cg_frotor / NBBY; len = howmany(fs->fs_fpg, NBBY) - start; loc = scanc(len, &cgp->cg_free[start], fragtbl[fs->fs_frag], - 1 << (allocsiz - 1)); + 1 << (allocsiz - 1 + (fs->fs_frag % NBBY))); if (loc == 0) { loc = fs->fs_dblkno / NBBY; len = start - loc + 1; start = loc; loc = scanc(len, &cgp->cg_free[start], fragtbl[fs->fs_frag], - 1 << (allocsiz - 1)); + 1 << (allocsiz - 1 + (fs->fs_frag % NBBY))); if (loc == 0) { panic("alloccg: map corrupted"); return (0); @@ -841,7 +841,7 @@ fragacct(fs, fragmap, fraglist, cnt) inblk = (int)(fragtbl[fs->fs_frag][fragmap]) << 1; fragmap <<= 1; for (siz = 1; siz < fs->fs_frag; siz++) { - if (((1 << siz) & inblk) == 0) + if ((inblk & (1 << (siz + (fs->fs_frag % NBBY)))) == 0) continue; field = around[siz]; subfield = inside[siz]; diff --git a/usr/src/sys/ufs/ffs/ffs_tables.c b/usr/src/sys/ufs/ffs/ffs_tables.c index 9d991cb39e..e7e70bfe20 100644 --- a/usr/src/sys/ufs/ffs/ffs_tables.c +++ b/usr/src/sys/ufs/ffs/ffs_tables.c @@ -1,6 +1,6 @@ /* Copyright (c) 1981 Regents of the University of California */ -/* @(#)ffs_tables.c 1.3 %G% */ +/* @(#)ffs_tables.c 1.4 %G% */ #include "../h/param.h" @@ -80,109 +80,39 @@ int inside[9] = { * quickly find an appropriate fragment. */ -unsigned char fragtbl1[256] = { - 0x0, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, - 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, - 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, - 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, - 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, - 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, - 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, - 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, - 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, - 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, - 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, - 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, - 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, - 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, - 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, - 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, - 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, - 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, - 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, - 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, - 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, - 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, - 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, - 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, - 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, - 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, - 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, - 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, - 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, - 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, - 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, - 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, -}; - -unsigned char fragtbl2[256] = { - 0x0, 0x1, 0x1, 0x2, 0x1, 0x1, 0x1, 0x3, - 0x1, 0x1, 0x1, 0x3, 0x2, 0x3, 0x3, 0x2, - 0x1, 0x1, 0x1, 0x3, 0x1, 0x1, 0x1, 0x3, - 0x1, 0x1, 0x1, 0x3, 0x3, 0x3, 0x3, 0x3, - 0x1, 0x1, 0x1, 0x3, 0x1, 0x1, 0x1, 0x3, - 0x1, 0x1, 0x1, 0x3, 0x3, 0x3, 0x3, 0x3, - 0x2, 0x3, 0x3, 0x2, 0x3, 0x3, 0x3, 0x3, - 0x3, 0x3, 0x3, 0x3, 0x2, 0x3, 0x3, 0x2, - 0x1, 0x1, 0x1, 0x3, 0x1, 0x1, 0x1, 0x3, - 0x1, 0x1, 0x1, 0x3, 0x3, 0x3, 0x3, 0x3, - 0x1, 0x1, 0x1, 0x3, 0x1, 0x1, 0x1, 0x3, - 0x1, 0x1, 0x1, 0x3, 0x3, 0x3, 0x3, 0x3, - 0x1, 0x1, 0x1, 0x3, 0x1, 0x1, 0x1, 0x3, - 0x1, 0x1, 0x1, 0x3, 0x3, 0x3, 0x3, 0x3, - 0x3, 0x3, 0x3, 0x3, 0x3, 0x3, 0x3, 0x3, - 0x3, 0x3, 0x3, 0x3, 0x3, 0x3, 0x3, 0x3, - 0x1, 0x1, 0x1, 0x3, 0x1, 0x1, 0x1, 0x3, - 0x1, 0x1, 0x1, 0x3, 0x3, 0x3, 0x3, 0x3, - 0x1, 0x1, 0x1, 0x3, 0x1, 0x1, 0x1, 0x3, - 0x1, 0x1, 0x1, 0x3, 0x3, 0x3, 0x3, 0x3, - 0x1, 0x1, 0x1, 0x3, 0x1, 0x1, 0x1, 0x3, - 0x1, 0x1, 0x1, 0x3, 0x3, 0x3, 0x3, 0x3, - 0x3, 0x3, 0x3, 0x3, 0x3, 0x3, 0x3, 0x3, - 0x3, 0x3, 0x3, 0x3, 0x3, 0x3, 0x3, 0x3, - 0x2, 0x3, 0x3, 0x2, 0x3, 0x3, 0x3, 0x3, - 0x3, 0x3, 0x3, 0x3, 0x2, 0x3, 0x3, 0x2, - 0x3, 0x3, 0x3, 0x3, 0x3, 0x3, 0x3, 0x3, - 0x3, 0x3, 0x3, 0x3, 0x3, 0x3, 0x3, 0x3, - 0x3, 0x3, 0x3, 0x3, 0x3, 0x3, 0x3, 0x3, - 0x3, 0x3, 0x3, 0x3, 0x3, 0x3, 0x3, 0x3, - 0x2, 0x3, 0x3, 0x2, 0x3, 0x3, 0x3, 0x3, - 0x3, 0x3, 0x3, 0x3, 0x2, 0x3, 0x3, 0x2, -}; - -unsigned char fragtbl4[256] = { - 0x0, 0x1, 0x1, 0x2, 0x1, 0x1, 0x2, 0x4, - 0x1, 0x1, 0x1, 0x3, 0x2, 0x3, 0x4, 0x8, - 0x1, 0x1, 0x1, 0x3, 0x1, 0x1, 0x3, 0x5, - 0x1, 0x1, 0x1, 0x3, 0x3, 0x3, 0x5, 0x9, - 0x1, 0x1, 0x1, 0x3, 0x1, 0x1, 0x3, 0x5, - 0x1, 0x1, 0x1, 0x3, 0x3, 0x3, 0x5, 0x9, - 0x2, 0x3, 0x3, 0x2, 0x3, 0x3, 0x2, 0x6, - 0x3, 0x3, 0x3, 0x3, 0x2, 0x3, 0x6, 0xa, - 0x1, 0x1, 0x1, 0x3, 0x1, 0x1, 0x3, 0x5, - 0x1, 0x1, 0x1, 0x3, 0x3, 0x3, 0x5, 0x9, - 0x1, 0x1, 0x1, 0x3, 0x1, 0x1, 0x3, 0x5, - 0x1, 0x1, 0x1, 0x3, 0x3, 0x3, 0x5, 0x9, - 0x2, 0x3, 0x3, 0x2, 0x3, 0x3, 0x2, 0x6, - 0x3, 0x3, 0x3, 0x3, 0x2, 0x3, 0x6, 0xa, - 0x4, 0x5, 0x5, 0x6, 0x5, 0x5, 0x6, 0x4, - 0x5, 0x5, 0x5, 0x7, 0x6, 0x7, 0x4, 0xc, - 0x1, 0x1, 0x1, 0x3, 0x1, 0x1, 0x3, 0x5, - 0x1, 0x1, 0x1, 0x3, 0x3, 0x3, 0x5, 0x9, - 0x1, 0x1, 0x1, 0x3, 0x1, 0x1, 0x3, 0x5, - 0x1, 0x1, 0x1, 0x3, 0x3, 0x3, 0x5, 0x9, - 0x1, 0x1, 0x1, 0x3, 0x1, 0x1, 0x3, 0x5, - 0x1, 0x1, 0x1, 0x3, 0x3, 0x3, 0x5, 0x9, - 0x3, 0x3, 0x3, 0x3, 0x3, 0x3, 0x3, 0x7, - 0x3, 0x3, 0x3, 0x3, 0x3, 0x3, 0x7, 0xb, - 0x2, 0x3, 0x3, 0x2, 0x3, 0x3, 0x2, 0x6, - 0x3, 0x3, 0x3, 0x3, 0x2, 0x3, 0x6, 0xa, - 0x3, 0x3, 0x3, 0x3, 0x3, 0x3, 0x3, 0x7, - 0x3, 0x3, 0x3, 0x3, 0x3, 0x3, 0x7, 0xb, - 0x4, 0x5, 0x5, 0x6, 0x5, 0x5, 0x6, 0x4, - 0x5, 0x5, 0x5, 0x7, 0x6, 0x7, 0x4, 0xc, - 0x8, 0x9, 0x9, 0xa, 0x9, 0x9, 0xa, 0xc, - 0x9, 0x9, 0x9, 0xb, 0xa, 0xb, 0xc, 0x8, +unsigned 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, }; unsigned char fragtbl8[256] = { @@ -224,5 +154,5 @@ unsigned char fragtbl8[256] = { * the actual fragtbl array */ unsigned char *fragtbl[MAXFRAG + 1] = { - 0, fragtbl1, fragtbl2, 0, fragtbl4, 0, 0, 0, fragtbl8, + 0, fragtbl124, fragtbl124, 0, fragtbl124, 0, 0, 0, fragtbl8, }; diff --git a/usr/src/sys/ufs/lfs/lfs_alloc.c b/usr/src/sys/ufs/lfs/lfs_alloc.c index c17a674549..2af43bfb10 100644 --- a/usr/src/sys/ufs/lfs/lfs_alloc.c +++ b/usr/src/sys/ufs/lfs/lfs_alloc.c @@ -1,6 +1,6 @@ /* Copyright (c) 1981 Regents of the University of California */ -static char vers[] = "@(#)lfs_alloc.c 1.19 %G%"; +static char vers[] = "@(#)lfs_alloc.c 1.20 %G%"; /* alloc.c 4.8 81/03/08 */ @@ -788,13 +788,13 @@ mapsearch(fs, cgp, bpref, allocsiz) start = cgp->cg_frotor / NBBY; len = howmany(fs->fs_fpg, NBBY) - start; loc = scanc(len, &cgp->cg_free[start], fragtbl[fs->fs_frag], - 1 << (allocsiz - 1)); + 1 << (allocsiz - 1 + (fs->fs_frag % NBBY))); if (loc == 0) { loc = fs->fs_dblkno / NBBY; len = start - loc + 1; start = loc; loc = scanc(len, &cgp->cg_free[start], fragtbl[fs->fs_frag], - 1 << (allocsiz - 1)); + 1 << (allocsiz - 1 + (fs->fs_frag % NBBY))); if (loc == 0) { panic("alloccg: map corrupted"); return (0); @@ -841,7 +841,7 @@ fragacct(fs, fragmap, fraglist, cnt) inblk = (int)(fragtbl[fs->fs_frag][fragmap]) << 1; fragmap <<= 1; for (siz = 1; siz < fs->fs_frag; siz++) { - if (((1 << siz) & inblk) == 0) + if ((inblk & (1 << (siz + (fs->fs_frag % NBBY)))) == 0) continue; field = around[siz]; subfield = inside[siz]; -- 2.20.1