double/CHANGES100600 0 0 5066 5575063107 11411 0ustar rootroot 7 Jun 1994: - Made double-0.2b distribution for Linux 1.1.15 - Added MAGIC number in linux/MAGIC. It's not a 16 bit int, though. 3 Jun 1994: - fixed plugging race in ll_rw_blk.c. - Tested with IDE patches. 31 May 1994: - Made double-0.2b for testing with Linux 1.1.13 - Several kernel structures have changed since 1.1.12. 29 May 1994: - There has been a huge gap. We'll try to fill it. - Several variable initialization fixes have been made sometime. Email address updated. - included improved pred.c from Peter Trattler 23 Mar 1994: - double-0.2a, with patches against Linux 1.0 19 Mar 1994: - cluster functions/buffers handling cleaned up 14 Mar 1994: - free block lookup improved (dbtools.c: get_newbit) 12 Mar 1994: - buffer flushing fixed in umount/dbumount - some work on dbck; it can now check blocks 11 Mar 1994: - bug fix in fs/super.c; double device could be umounted 2x, resulting in a segmentation fault - LZV-0.3 compression, by Hermann Vogt, included - bug fix in dbck.c (floating point error when device empty). - minor changes to mkdble.c 4 Mar 1994: - bug fix in pred.c (last flag byte was not written) 3 Mar 1994: Version 0.2 uploaded 2 Mar 1994: - bug fix in double.c do_db_request; swap can now be mounted on DouBle devices. - minor typo corrections to test distribution 0.2 27 Feb 1994: - bug fix: added synchronization to statfs 26 Feb 1994: Test version 0.2 ftp'ed to Thomas Graichen 25 Feb 1994: - getting ready to upload version 0.2 (file cleaning) - Default parameters to mkdble changed 24 Feb 1994: - Function ll_rw_dble written. It replaces calls to ll_rw_block, but may still need some work (Error checking) 23 Feb 1994: - Implementation of the predictor's algorithm, by Dave Rand, as suggested by Jean-Loup Gailly who provided sources and advices 20 Feb 1994: - Implementation of mount/umount/df support files: dbsuper.c, mount.c, fs/super.c 18 Feb 1994: - Fixes to variable initialization - Implementation of LZRW2, LZRW3A, by Ross Williams, as suggested by Leo Broukhis who provided sources and advices 16 Feb 1994: - dbck utility largely modified 15 Feb 1994: - Few minor changes as suggested by Thomas Graichen - function get_newbit rewritten 10 Feb 1994: Version 0.1a - Patch against kernel 0.99pl15 - Few minor changes 5 Feb 1994: Patch 1 - Bug fix (when using more than one device). Bug reported by 1 Feb 1994: Version 0.1: - Buffer flushing improved - Synchronization between kernel and user requests fixed - Some speed improvement - Few minor changes 26 Jan 1994: Version 0.0 submitted double/Makefile100644 0 0 1474 5572605510 12062 0ustar rootroot# Tools for the "double" Linux disk compression device driver. # by Jean-Marc Verbavatz 11 Jan 1994. CFLAGS = -O2 -N LFLAGS = -s all = mkdble dbck dbmount dbumount dbdebug dbstat dbmode all: $(all) mkdble: mkdble.o tools.o cc $(LFLAGS) -o mkdble mkdble.o tools.o dbck: dbck.o tools.o lzw.o lzv.o pred.o lzrw2.o lzrw3-a.o cc $(LFLAGS) -o dbck dbck.o tools.o lzw.o lzv.o pred.o lzrw2.o lzrw3-a.o dbmount: dbmount.o cc $(LFLAGS) -o dbmount dbmount.o dbumount: dbumount.o cc $(LFLAGS) -o dbumount dbumount.o dbdebug: dbdebug.o cc $(LFLAGS) -o dbdebug dbdebug.o dbstat: dbstat.o cc $(LFLAGS) -o dbstat dbstat.o dbmode: dbmode.o tools.o cc $(LFLAGS) -o dbmode dbmode.o tools.o mount: mount.o cc $(LDFLAGS) -o mount mount.c clean: $(RM) *.o $(all) install: install $(all) /usr/local/bin double/dbck.c100644 0 0 13767 5572605562 11530 0ustar rootroot/* double/dbck.c checks consistency of DouBle file 20 Dec 1993 * * Copyright (C) 1994 Jean-Marc Verbavatz * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2 of the License, or * (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */ #include #include #include #include struct dble_device db; extern struct db_header dbh; unsigned char memory[65536]; /* for block check */ int options = 0; void read_opt(char *name, char *s) { while(*s) { switch(*s) { case 'a': options |= 1; break; case 'v': options |= 2; break; case 't': options |= 4; break; case 'r': options |= 8; break; case 0: return; default: usage(name); } s++; } } /* Check consistency of block n */ int get_block(struct dble_device *db, u_long n, int options) { u_long *p; int i,j; struct BAT *b; u_char buffer[DB_MAXSZ], buffer1[DB_MAXSZ], *s; if(!get_BAT(db, n)) return -1; b = (struct BAT *)(db->BAT_block + db->BATsize*(n%(db->isize/db->BATsize))); p=&b->iblock; s = buffer; for(i=j=0; iratio; i++, j++, p++) { if(*p==0) { /* Empty; check other iblocks */ while(++iratio) if(*(++p)!=0) return -2; /* Error */ if(j==0) return 0; /* Unused */ break; } if(get_bit(db, *p)) return -3; /* Error; not in bitmap */ db_rw_iblock(db, READ, *p, s); s += db->isize; } /* BAT entry not empty */ if(options & 4) { /* Check blocks */ switch(b->type) { /* Check data */ case 0: if(iratio) return -4; i = db->osize; break; case 1: i = RLZW((code *) buffer, buffer1, db->osize); break; case 10: i = rpred(buffer, buffer1, db->osize); break; case 101: break; case 102: i = rLZV(buffer, buffer1, db->osize); break; case 212: i = rlzrw2(buffer, buffer1, db->osize); break; case 312: i = rlzrw3a(buffer, buffer1, db->osize); break; default: fprintf(stderr, "Type %d unknown\n", b->type); return -6; } /* Is i compatible with j ? */ if(i <= (j-1)*db->isize || i > j*db->isize) /* We have a problem ! */ return -5; } return j; /* j iblocks in use, OK */ } main(argc, argv) int argc; char **argv; { int i; u_long n, bitmaps, errors; u_long empty, total, blocks; float factor; char *file = NULL; for(i = 1; i < argc; i++) switch(*argv[i]) { case '-': read_opt(argv[0], argv[i]+1); break; default: if(file != NULL) usage(argv[0]); file = argv[i]; } if(file == NULL || !db_open(&db, file)) usage(argv[0]); if(options & 4) { /* We'll need the decomp functions */ i = iLZW(memory); if(i > 65536) options &= ~4; i = iLZV(memory); if(i > 65536) options &= ~4; i = ilzrw2(memory); if(i > 65536) options &= ~4; i = ilzrw3a(memory); if(i > 65536) options &= ~4; i = ipred(memory); if(i > 65536) options &= ~4; } printf("DouBle device version %d.%d\n", dbh.version>>8, dbh.version&0xff); if(dbh.version < 2) printf("Old device version - converting recommended\n"); if(options & 2) printf("Compression algorithm: %d\n", db.code); total = blocks = empty = 0; if(options & 2) printf("Checking blocks ...\n"); for(n = errors = 0; n 0) total += i, blocks++; else printf("\nError %d unknown", i); } if(i < 0) { errors++; printf(", cluster %ld ", n); fflush(stdout); } } if(errors && (options & 2)) printf("%ld Error(s) found\n", errors); total += db.addr_blocks; if(options & 2) { printf("\nChecking bitmap ... "); fflush(stdout); } for(bitmaps = n = 0; n < db.iblocks; n++) if(!get_bit(&db, n)) bitmaps++; if(bitmaps == total) { if(options & 2) printf("OK\n"); } else printf("%ld blocks set used are clear\n", bitmaps-total); if(total > db.addr_blocks) { factor = (float)db.ratio/((float)(total-db.addr_blocks)/blocks); printf("\nAverage compression factor (excluding headers) = %2.2f\n", factor); printf("Approximately %.0fK still available\n", factor*db.isize*(db.iblocks-total)/1024); } else { factor = 0; if(options & 2) printf("\nDevice is empty\n"); } printf("%ld/%ld (%2d%%) clusters (%d) used, %ld/%ld (%2d%%) blocks (%d) used.\n", blocks, db.oblocks, (int)(100*blocks/db.oblocks), db.osize, total, db.iblocks, (int)(100*total/db.iblocks), db.isize); db_close(); if((options & 2) && factor > 0) { printf("\nConclusion: "); if(db.iblocks > total) { factor = empty*db.ratio/factor/(db.iblocks-total); if(factor < 0.75) printf("Compression ratio better than expected !\n\n"); else if(factor > 1.3) printf("Poor compression ratio; could run out of space (beware) !\n\n"); else printf("So far, the compression ratio looks OK to me.\n\n"); } else printf("!! This thing is FULL !! Action required immediately!\n\n"); } if(errors) exit(4); exit(0); } usage(char *s) { if(errno) perror(s); printf("usage: %s [options] device_file\n", s); printf("\tcheck consistency of \"DouBle\" device_file\n"); printf("\toptions:\n\t\t-v:\tverbose.\n\t\t-t:\tcheck blocks (slooow).\n"); printf("\t\t-a:\tautomatic repair.\n\t\t-r:\tinteractive repair.\n"); if(errno) exit(8); exit(16); } double/dbstat.c100644 0 0 3717 5572605660 12057 0ustar rootroot/* double/dbstat.c DouBle driver device access. 22 Jan 1994 * * Copyright (C) 1994 Jean-Marc Verbavatz * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2 of the License, or * (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */ #include #include #include #include #include main(argc, argv) int argc; char **argv; { int fd; int result; struct db_stat dble_stat; if(argc != 2 || (fd = open(argv[1], O_RDWR))<0) { if(errno) perror(argv[0]); usage(argv[0]); } if((result = ioctl(fd, DBLE_STAT, &dble_stat))) perror(argv[0]); printf("block read requests: %ld\n", dble_stat.rphysical); printf("block write requests: %ld\n", dble_stat.wphysical); printf("clusters read: %ld\n", dble_stat.roblock); printf("clusters written: %ld\n", dble_stat.woblock); printf("cluster read requests: %ld\n", dble_stat.rvirtual); printf("cluster write requests: %ld\n", dble_stat.wvirtual); printf("blocks hits/nohits: %ld/%ld\n", dble_stat.ihit, dble_stat.inohit); printf("clusters hits/nohits: %ld/%ld\n", dble_stat.ohit, dble_stat.onohit); /*printf("\nSwap compression: %ld pages, %d blocks/page\n", dble_stat.swap_pages, dble_stat.swap_blocks/dble_stat.swap_pages);*/ close(fd); } usage(s) char *s; { fprintf(stderr, "\nusage: %s /dev/double[0-7]\n", s); fprintf(stderr, "\treports DouBle driver device access\n"); exit(-1); } double/tools.c100600 0 0 10035 5575033557 11740 0ustar rootroot/* double/tools.c tools for DouBle device utilities * * Copyright (C) 1994 Jean-Marc Verbavatz * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2 of the License, or * (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. * * 8 January 1994 */ #include #include #include #include #include #include #include #include u_char mask[8] = { 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 1 }; struct db_header dbh; int fd; int get_bitmap(struct dble_device *db, long n) { if(db->bitmap_pos==n) return 1; if(db->bitmap_mod) { if(db->bitmap_pos>=0) { if(!db_rw_iblock(db, WRITE, db->bitmap_pos+db->addr_bitmap, db->bitmap)) return 0; } else { fprintf(stderr, "\n bitmap_pos = %ld <0\n", db->bitmap_pos); return 0; } db->bitmap_mod=0; } if(n<0) return 1; if(db_rw_iblock(db, READ, n+db->addr_bitmap, db->bitmap)) { db->bitmap_pos = n; return 1; } return 0; } int get_BAT(struct dble_device *db, long n) { long i; /* This is not too efficient; some space is lost as db->isize is not a multiple BAT, but this is much easier */ i = n/(db->isize/db->BATsize); if(db->BAT_pos!=i || n<0) { if(db->BAT_mod) { if(db->BAT_pos>=0) { if(!db_rw_iblock(db, WRITE, db->BAT_pos+db->addr_BAT, db->BAT_block)) return 0; } else { fprintf(stderr, "\n BAT_pos = %ld <0\n", db->BAT_pos); return 0; } db->BAT_mod=0; } if(n<0) return 1; if(!db_rw_iblock(db, READ, i+db->addr_BAT, db->BAT_block)) return; db->BAT_pos = i; } return 1; } int db_rw_iblock(db, cmd, n, s) /* Read/Write db->isize bytes from device/file */ struct dble_device *db; int cmd; long n; u_char *s; { if(lseek(fd, n*db->isize, 0L)<0) return 0; if(cmd==READ) { if(read(fd, s, db->isize)==db->isize) return 1; else return 0; } if(write(fd, s, db->isize)==db->isize) return 1; return 0; } u_long get_newbit(db) struct dble_device *db; { int j, k, l; u_long i, b; i = 0; for(b = 0; ; b++) { get_bitmap(db, b); for(j = 0; j < db->isize; j++) if((k = db->bitmap[j])!=0) { for(l=0x80; l; l>>=1, i++) if(k&l) { k &= ~l; db->bitmap[j] = k; db->bitmap_mod = 1; i += j<<3; return i; } } i += j<<3; if(i >= db->iblocks) return 0; } } void clr_bit(struct dble_device *db, u_long n) { u_long i; i=n/(db->isize<<3); n=n%(db->isize<<3); get_bitmap(db, i); db->bitmap[n>>3] &= ~mask[n&7]; db->bitmap_mod=1; } void set_bit(struct dble_device *db, u_long n) { u_long i; i=n/(db->isize<<3); n=n%(db->isize<<3); get_bitmap(db, i); db->bitmap[n>>3] |= mask[n&7]; db->bitmap_mod=1; } int get_bit(struct dble_device *db, u_long n) { u_long i; i=n/(db->isize<<3); n=n%(db->isize<<3); get_bitmap(db, i); return (db->bitmap[n>>3] & mask[n&7]); } void db_close() { close(fd); } int db_open(db, s) struct dble_device *db; char *s; { if((fd = open(s, O_RDWR))<0) return 0; db->isize = sizeof(struct db_header); db_rw_iblock(db, READ, 0L, (u_char *)&dbh); if(dbh.magic != DB_MAGIC) return 0; db->isize = dbh.isize; db->osize = dbh.osize; if(db->osize>DB_MAXSZ) return 0; db->iblocks = dbh.iblocks; db->oblocks = dbh.oblocks; db->addr_bitmap = dbh.addr_bitmap; db->addr_BAT = dbh.addr_BAT; db->addr_blocks = dbh.addr_blocks; db->BATsize = dbh.BATsize; db->ratio = dbh.ratio; db->code = dbh.code; db->bitmap_pos = -1; db->bitmap_mod = 0; db->BAT_pos = -1; db->BAT_mod = 0; db->bitmap = malloc(db->isize); db->BAT_block = malloc(db->isize); if(db->bitmap == NULL || db->BAT_block == NULL) return 0; return 1; } double/dbdebug.c100644 0 0 2604 5572605600 12156 0ustar rootroot/* double/dbdebug.c change debugging level on DouBle device. 14 Jan 1994 * * Copyright (C) 1994 Jean-Marc Verbavatz * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2 of the License, or * (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */ #include #include #include #include #include main(argc, argv) int argc; char **argv; { int fd, level; int result; level = -1; if(argc != 3 || (fd = open(argv[1], O_RDWR))<0 || (level = atoi(argv[2])) < 0) { if(errno) perror(argv[0]); usage(argv[0]); } if((result = ioctl(fd, DBLE_DEBUG, level))) perror(argv[0]); close(fd); } usage(s) char *s; { fprintf(stderr, "\nusage: %s /dev/double[0-7] level\n", s); fprintf(stderr, "\tChange Message level on DouBle device\n"); exit(-1); } double/mount100755 0 0 32004 5533571220 11520 0ustar rootroot d -̀\ `-@D$4 `zP`[̀rUsage: mount [-afnpruv] [-t type] [-o options] [[dev] dir] UhTh ``j ]afnput:rvo:,ro/etc/ufstab/etc/fstabr/etc/mtabmount: Don't know what to mount on %s mount: You must be root to mount a filesystem. mount: A lock-file exists, mount denied. ro,nosuid,noexec,nodevmount: Can't usermount %s. UWVS]u LhVS<` <U7$DTtd e UjD `Rh a=$ thh$ t `hh$ b ` hD `Rh$ `    {`ft  9H `PH `l!H `9H `!= tl!p!l!hW`ƃu WV.`ÃSRp!RA `tnRp!R+ `ujSRh"l `p!l!p!" = uj[Sh : ` vjRh" `l!" = uj[Sh ` V_h$ X =l! hh_ƃu WV`ÃtuSRp!R% `tBRp!R `uj[Sh"P `p!l!p!" 뙐jSh"% `l!" =l!u[p!Rhh `_j.9H `p!!uhj!__fth h `_j = u$/uh<h `_j_= = thSA_ƃu SfV_Ãta= tSRh `uӃ= t{ tC 8uC f= t S랐S뒐V_2=p!#= 1hh_ƃuhV_ÃtXRl!R`uۋSRp!R`uĿhS Rh$ `j[Sh `V_u p!Rh}h `_j E l!Up!UE$ EEEPuuj_[j_/etc/mtab~Uhhh}` |P_]Ð1]Uh`]minixswapmount: swapon(%s) failed: %s Added swap: %s mount: mkdir(%s) failed. Made directory: %s mount: stat(%s) failed. /mount: root already mounted by kernel ignoremount: ignored %s mount: mount(%s,%s) failed: %s Mounted %s on %s. amount: open(%s) failed. U@WVS]{tC8u UBe][ S0= t= t 1= +Urku\S`}-< `R%`P]Shph `__1Y= CURhEP][St`< `wXhURRc_}][Sh>= tGURRhh `_ ,][Shh `_1Uru9 u0= hh `X_]s u)= Rh h `_h! P][SURR]S{_}0< `Rx`P][SURh( h `_1= t][SURhH h `_= uo t]suOUrkt8h[ h_ƃuhh] ]SV_V_e[^_]mount: %s: %s US]t < `R}`PSh h `_jh_u h$`j_defaults%s %s %s %s %d %d USMYSYSQ  :tPYSYS Qh _]]UVSuhV_Ãu VSN_t P吐S_e[^]rwsuidnosuidnodevnoexecsyncremountnoautoUWVS]!  >;5UxE C@;t;,u;,uCx u0= t  xu  x u% `x u% 0x u  x u  x u  x u  sx u  Sx u 0xRh!_hh!_t ;=!t0!ƀ!l[^_]S"u1҃="t"B8uЅt"Ѓ"u[S!=!t Ѓ;uh_[=x!ux!/usr/lib//lib// *0S\$̀[̀}أ!Ð%1̀}أ!Ð%/̀}أ!Ð%2̀}أ!Ð%SV\$̀} أ![S\$L$ T$̀} أ![WVT$ t$1Ou^_WVSt$\$T$t%1IQRVu Su[^_' : can't load library 'Incompatible version. Too many libraries. No such library. Permission denied. Exec format error. Unspecified error. Corrupt fixup table. VSt$ F8tU8t'jhajhxD PK}[^UWVS\$S|$99t"jhajdh 3x|$WD PN}S:ltT19u~M||$?t8L$1ې|$u|$D;)|$D;9uF9u[^_]VSt$ F88t#jhajh+xD PK}1| tD L CN9C#TDN9[^LD_LIBRARY_PATH). : incompatible minor version numbers (: Warning: ) ( U4WVS}EDžft%_f9uf9t Dž1IU:tH߾AItuu1 r؅u<=:u1҃t ti:`Dž1ۀ:t*9:uC>u݋\$)ĉ !ω4)Dž<$Dž:tb㋕8:u%/BB B>u8/D19!~d4 :>C9!*@{Dž4!Dž!=!6~1ۋƅ QCV?PVVM9~ =!t!jhQhu 6Vj$ jhNjh>jh.jh%jh9jhMj hU?_ ف9u9ttQjh6~WhPhM Qhj$IjhVh} ?Wjjhj hr8hDž!=!t=jh qVh9Whje8ujjh!h!zjh!~h![^_]libc.so.4DLL Jump 4.4pl2defaults|!``!?` !!double/COPYING100600 0 0 43076 5514711347 11473 0ustar rootroot GNU GENERAL PUBLIC LICENSE Version 2, June 1991 Copyright (C) 1989, 1991 Free Software Foundation, Inc. 675 Mass Ave, Cambridge, MA 02139, USA Everyone is permitted to copy and distribute verbatim copies of this license document, but changing it is not allowed. Preamble The licenses for most software are designed to take away your freedom to share and change it. By contrast, the GNU General Public License is intended to guarantee your freedom to share and change free software--to make sure the software is free for all its users. This General Public License applies to most of the Free Software Foundation's software and to any other program whose authors commit to using it. (Some other Free Software Foundation software is covered by the GNU Library General Public License instead.) You can apply it to your programs, too. When we speak of free software, we are referring to freedom, not price. Our General Public Licenses are designed to make sure that you have the freedom to distribute copies of free software (and charge for this service if you wish), that you receive source code or can get it if you want it, that you can change the software or use pieces of it in new free programs; and that you know you can do these things. To protect your rights, we need to make restrictions that forbid anyone to deny you these rights or to ask you to surrender the rights. These restrictions translate to certain responsibilities for you if you distribute copies of the software, or if you modify it. For example, if you distribute copies of such a program, whether gratis or for a fee, you must give the recipients all the rights that you have. You must make sure that they, too, receive or can get the source code. And you must show them these terms so they know their rights. We protect your rights with two steps: (1) copyright the software, and (2) offer you this license which gives you legal permission to copy, distribute and/or modify the software. Also, for each author's protection and ours, we want to make certain that everyone understands that there is no warranty for this free software. If the software is modified by someone else and passed on, we want its recipients to know that what they have is not the original, so that any problems introduced by others will not reflect on the original authors' reputations. Finally, any free program is threatened constantly by software patents. We wish to avoid the danger that redistributors of a free program will individually obtain patent licenses, in effect making the program proprietary. To prevent this, we have made it clear that any patent must be licensed for everyone's free use or not licensed at all. The precise terms and conditions for copying, distribution and modification follow. GNU GENERAL PUBLIC LICENSE TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION 0. This License applies to any program or other work which contains a notice placed by the copyright holder saying it may be distributed under the terms of this General Public License. The "Program", below, refers to any such program or work, and a "work based on the Program" means either the Program or any derivative work under copyright law: that is to say, a work containing the Program or a portion of it, either verbatim or with modifications and/or translated into another language. (Hereinafter, translation is included without limitation in the term "modification".) Each licensee is addressed as "you". Activities other than copying, distribution and modification are not covered by this License; they are outside its scope. The act of running the Program is not restricted, and the output from the Program is covered only if its contents constitute a work based on the Program (independent of having been made by running the Program). Whether that is true depends on what the Program does. 1. You may copy and distribute verbatim copies of the Program's source code as you receive it, in any medium, provided that you conspicuously and appropriately publish on each copy an appropriate copyright notice and disclaimer of warranty; keep intact all the notices that refer to this License and to the absence of any warranty; and give any other recipients of the Program a copy of this License along with the Program. You may charge a fee for the physical act of transferring a copy, and you may at your option offer warranty protection in exchange for a fee. 2. You may modify your copy or copies of the Program or any portion of it, thus forming a work based on the Program, and copy and distribute such modifications or work under the terms of Section 1 above, provided that you also meet all of these conditions: a) You must cause the modified files to carry prominent notices stating that you changed the files and the date of any change. b) You must cause any work that you distribute or publish, that in whole or in part contains or is derived from the Program or any part thereof, to be licensed as a whole at no charge to all third parties under the terms of this License. c) If the modified program normally reads commands interactively when run, you must cause it, when started running for such interactive use in the most ordinary way, to print or display an announcement including an appropriate copyright notice and a notice that there is no warranty (or else, saying that you provide a warranty) and that users may redistribute the program under these conditions, and telling the user how to view a copy of this License. (Exception: if the Program itself is interactive but does not normally print such an announcement, your work based on the Program is not required to print an announcement.) These requirements apply to the modified work as a whole. If identifiable sections of that work are not derived from the Program, and can be reasonably considered independent and separate works in themselves, then this License, and its terms, do not apply to those sections when you distribute them as separate works. But when you distribute the same sections as part of a whole which is a work based on the Program, the distribution of the whole must be on the terms of this License, whose permissions for other licensees extend to the entire whole, and thus to each and every part regardless of who wrote it. Thus, it is not the intent of this section to claim rights or contest your rights to work written entirely by you; rather, the intent is to exercise the right to control the distribution of derivative or collective works based on the Program. In addition, mere aggregation of another work not based on the Program with the Program (or with a work based on the Program) on a volume of a storage or distribution medium does not bring the other work under the scope of this License. 3. You may copy and distribute the Program (or a work based on it, under Section 2) in object code or executable form under the terms of Sections 1 and 2 above provided that you also do one of the following: a) Accompany it with the complete corresponding machine-readable source code, which must be distributed under the terms of Sections 1 and 2 above on a medium customarily used for software interchange; or, b) Accompany it with a written offer, valid for at least three years, to give any third party, for a charge no more than your cost of physically performing source distribution, a complete machine-readable copy of the corresponding source code, to be distributed under the terms of Sections 1 and 2 above on a medium customarily used for software interchange; or, c) Accompany it with the information you received as to the offer to distribute corresponding source code. (This alternative is allowed only for noncommercial distribution and only if you received the program in object code or executable form with such an offer, in accord with Subsection b above.) The source code for a work means the preferred form of the work for making modifications to it. For an executable work, complete source code means all the source code for all modules it contains, plus any associated interface definition files, plus the scripts used to control compilation and installation of the executable. However, as a special exception, the source code distributed need not include anything that is normally distributed (in either source or binary form) with the major components (compiler, kernel, and so on) of the operating system on which the executable runs, unless that component itself accompanies the executable. If distribution of executable or object code is made by offering access to copy from a designated place, then offering equivalent access to copy the source code from the same place counts as distribution of the source code, even though third parties are not compelled to copy the source along with the object code. 4. You may not copy, modify, sublicense, or distribute the Program except as expressly provided under this License. Any attempt otherwise to copy, modify, sublicense or distribute the Program is void, and will automatically terminate your rights under this License. However, parties who have received copies, or rights, from you under this License will not have their licenses terminated so long as such parties remain in full compliance. 5. You are not required to accept this License, since you have not signed it. However, nothing else grants you permission to modify or distribute the Program or its derivative works. These actions are prohibited by law if you do not accept this License. Therefore, by modifying or distributing the Program (or any work based on the Program), you indicate your acceptance of this License to do so, and all its terms and conditions for copying, distributing or modifying the Program or works based on it. 6. Each time you redistribute the Program (or any work based on the Program), the recipient automatically receives a license from the original licensor to copy, distribute or modify the Program subject to these terms and conditions. You may not impose any further restrictions on the recipients' exercise of the rights granted herein. You are not responsible for enforcing compliance by third parties to this License. 7. If, as a consequence of a court judgment or allegation of patent infringement or for any other reason (not limited to patent issues), conditions are imposed on you (whether by court order, agreement or otherwise) that contradict the conditions of this License, they do not excuse you from the conditions of this License. If you cannot distribute so as to satisfy simultaneously your obligations under this License and any other pertinent obligations, then as a consequence you may not distribute the Program at all. For example, if a patent license would not permit royalty-free redistribution of the Program by all those who receive copies directly or indirectly through you, then the only way you could satisfy both it and this License would be to refrain entirely from distribution of the Program. If any portion of this section is held invalid or unenforceable under any particular circumstance, the balance of the section is intended to apply and the section as a whole is intended to apply in other circumstances. It is not the purpose of this section to induce you to infringe any patents or other property right claims or to contest validity of any such claims; this section has the sole purpose of protecting the integrity of the free software distribution system, which is implemented by public license practices. Many people have made generous contributions to the wide range of software distributed through that system in reliance on consistent application of that system; it is up to the author/donor to decide if he or she is willing to distribute software through any other system and a licensee cannot impose that choice. This section is intended to make thoroughly clear what is believed to be a consequence of the rest of this License. 8. If the distribution and/or use of the Program is restricted in certain countries either by patents or by copyrighted interfaces, the original copyright holder who places the Program under this License may add an explicit geographical distribution limitation excluding those countries, so that distribution is permitted only in or among countries not thus excluded. In such case, this License incorporates the limitation as if written in the body of this License. 9. The Free Software Foundation may publish revised and/or new versions of the General Public License from time to time. Such new versions will be similar in spirit to the present version, but may differ in detail to address new problems or concerns. Each version is given a distinguishing version number. If the Program specifies a version number of this License which applies to it and "any later version", you have the option of following the terms and conditions either of that version or of any later version published by the Free Software Foundation. If the Program does not specify a version number of this License, you may choose any version ever published by the Free Software Foundation. 10. If you wish to incorporate parts of the Program into other free programs whose distribution conditions are different, write to the author to ask for permission. For software which is copyrighted by the Free Software Foundation, write to the Free Software Foundation; we sometimes make exceptions for this. Our decision will be guided by the two goals of preserving the free status of all derivatives of our free software and of promoting the sharing and reuse of software generally. NO WARRANTY 11. BECAUSE THE PROGRAM IS LICENSED FREE OF CHARGE, THERE IS NO WARRANTY FOR THE PROGRAM, TO THE EXTENT PERMITTED BY APPLICABLE LAW. EXCEPT WHEN OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR OTHER PARTIES PROVIDE THE PROGRAM "AS IS" WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS WITH YOU. SHOULD THE PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING, REPAIR OR CORRECTION. 12. IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY AND/OR REDISTRIBUTE THE PROGRAM AS PERMITTED ABOVE, BE LIABLE TO YOU FOR DAMAGES, INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OR INABILITY TO USE THE PROGRAM (INCLUDING BUT NOT LIMITED TO LOSS OF DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY YOU OR THIRD PARTIES OR A FAILURE OF THE PROGRAM TO OPERATE WITH ANY OTHER PROGRAMS), EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES. END OF TERMS AND CONDITIONS Appendix: How to Apply These Terms to Your New Programs If you develop a new program, and you want it to be of the greatest possible use to the public, the best way to achieve this is to make it free software which everyone can redistribute and change under these terms. To do so, attach the following notices to the program. It is safest to attach them to the start of each source file to most effectively convey the exclusion of warranty; and each file should have at least the "copyright" line and a pointer to where the full notice is found. Copyright (C) 19yy This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. Also add information on how to contact you by electronic and paper mail. If the program is interactive, make it output a short notice like this when it starts in an interactive mode: Gnomovision version 69, Copyright (C) 19yy name of author Gnomovision comes with ABSOLUTELY NO WARRANTY; for details type `show w'. This is free software, and you are welcome to redistribute it under certain conditions; type `show c' for details. The hypothetical commands `show w' and `show c' should show the appropriate parts of the General Public License. Of course, the commands you use may be called something other than `show w' and `show c'; they could even be mouse-clicks or menu items--whatever suits your program. You should also get your employer (if you work as a programmer) or your school, if any, to sign a "copyright disclaimer" for the program, if necessary. Here is a sample; alter the names: Yoyodyne, Inc., hereby disclaims all copyright interest in the program `Gnomovision' (which makes passes at compilers) written by James Hacker. , 1 April 1989 Ty Coon, President of Vice This General Public License does not permit incorporating your program into proprietary programs. If your program is a subroutine library, you may consider it more useful to permit linking proprietary applications with the library. If this is what you want to do, use the GNU Library General Public License instead of this License. double/INTERNALS100600 0 0 5546 5533712471 11702 0ustar rootrootDouble version 0.2 INTERNALS 25 Feb 1994 ---------------------------- The DouBle device driver acts as an interface between the physical (compressed) data on a device or a regular file, and a pseudo "DouBle" block device, where non compressed data is written/read. DouBle was originally inspired from the loop driver, written and copyright by Theodore Ts'o. This is how it works: <-> <-> <-> (3) (2) (1) is either a real block device (such as a disk partition) or a regular file on an existing file system. Data on this device (or file) is compressed and should not be accessed directly. Before it can be used, this device also need to be formatted. is a virtual block device, where non compressed data can be written/read. The major number for DouBle devices is currently 19. is either a filesystem, or any utility that works with block devices (You could do a tar on a double device). Finally the does all the work. Of course, one needs to do a few things to set up links (1),(2),(3). 1 - The regular file needs to be "formatted" - I'll explain that further down. 2 - There is a utility (dbmount or mount) to establish links (1) and (2): dbmount mount -t dble 3 - There is a utility to break the links: (dbumount or umount). Following that, any request going to will be (de)compressed and piped to/from the transparently. How does the driver do compression ? On the side of link (1) it work with blocks (say 512 bytes). on the side of link (2), it works with clusters (usually 16 blocks long). The driver compresses each cluster and use as few blocks as necessary to hold either the compressed cluster or the non compressed cluster (in case of overrun). For that purpose, there are several table in a compressed device (hence the formating step): The physical file/device contains a header (a), a bitmap (b) and a block allocation table (c) referred to as BAT in the source. Regular files used as devices also contain a block map table (d). (a) The header contains a Magic number and relevant informations on the size and number of physical blocks (called isize and iblocks) and virtual block clusters (osize and oblocks). (b) The bitmap tells which iblocks are already allocated. (c) The BAT contains information on the type of compression, and on which iblocks the clusters are made of. Each oblock (cluster) is made of several (smaller) iblocks (from 1 to osize/isize), depending on the compression factor for the cluster. (d) The block map table is used by the driver to access a real block from the block number of a regular file. Finally, there is a utility (dbcheck) to check the integrity of data in these structures. double/pred.c120777 0 0 0 5554510512 20112 2/usr/src/linux/drivers/block/pred.custar rootrootdouble/README100600 0 0 26221 5575106562 11315 0ustar rootrootDouBle Alpha Version 0.2b 31 Mai 1994 ------------------------- Double is a block device driver for Linux that does on-the-fly compression. It does not implement a compressed file system as such, but a file system can be mounted on a compressed device. Version 0.2b contains very few improvements over version 0.2(a). It fixes several bugs, and comes with patches for Linux version 1.1.15. My apologies to people having made exciting contributions that I have not yet included. This is nothing more than a maintenance distribution... FEATURES -------- DouBle 0.2 comes with a choice of 5 different compression algorithms. - LZW is still included, but will probably not be supported in future releases: It is really slow and patented. - A derivative of the predictor used in PPP (by Dave Rand) has been chosen as the new default algorithm. Although it does not give the best compression either, it is much faster than LZW and is in the public domain. I intend to improve its performance in future releases. - LZRW2 and LZRW3A, written by Ross Williams. They both yield a good speed*compression. LZRW2 is faster, LZRW3A compresses better... - LZV, by Hermann Vogt. This new algorithm has similarities with LZRW, it is fast and compresses well also. mount/umount/df support for DouBle devices. - Version 0.2 provides optional support for some (few indeed) fs-like operations. THE DRIVER IS NOT A FILESYSTEM HOWEVER. There is only support for put_super, read_super and statfs, with a fs type named "dble" (see below). Unfortunately, this involves patches to the kernel (and to mount) that I am not really happy with. Therefore, this is only an option, and the driver can also be used without fs support. MISSING FEATURES Please, tell me if you think I should add something. ---------------- - Better recovery when DouBle device becomes out of space. I have something in mind, but suggestions are welcome. - A better fsck-like program. dbck is closer to fsck and does more checking than in version 0.2, but it still does not fix problems. - The predictor algorithm needs a boost in compression. - Documentation: there are still no man pages and it's probably going to take a while because I don't know how to write them (what good am I, really ?). WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING ! ! ! Back up your disks before you even think of trying it. I take no ! ! responsibility for data lost because of this driver. ! ! ! WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING INSTALLATION ------------ This distribution includes: - patches against Linux version 1.1.15. - A set of utilities. - A patch to the source of mount.c from the usermount package, by Peter Orbaek and a binary. see section 5b. 0 cd to /usr/src and tar xvfz double-0.2b.tar.gz ----------------------------------------------- 1 Patch the kernel (Linux 1.1.15 or higher), from /usr/src: ----------------------------------------------------------- patch -p0 = 1.1.14 (perhaps earlier, but the compression driver was not there). I have spent a long time trying to fix the problem in vain. I believe the problem is in the SCSI driver. For people having both SCSI and IDE disks (it's not my case), it seems to disappear when swapping is done on IDE disks. I'd be most grateful to anybody who could help in fixing that. Send bug reports (or better fixes !) to , and/or to the COMPRESSION channel on niksula.hut.fi ACKNOWLEDGMENTS --------------- Leo Broukhis and Jean-Loup Gailly have contributed a kind and precious expertise in the use of new compression algorithms. Thomas Graichen has been most helpful in making suggestions and comprehensive tests of this driver. Didier Genard has submitted a very comprehensive list of improvements that I haven't yet included in this version, but I still want to thank him. Michael Beck (I don't have is address handy) has made useful suggestions. Richard has provided the LZV algorithm written by Hermann Vogt. Many other people have provided useful reports; I hope you will continue to help me inprove the DouBle driver. AUTHORS ------- Jean-Marc Verbavatz (Jan 1994) Peter Trattler has improved the speed of the predictor compression algorithm. Parts of the driver source were adapted from the loop driver copyright by Theodore Ts'o. LZV was written by Hermann Vogt. The LZRW2, LZRW3-A algorithms were written by Ross Williams The predictor algorithm was originally written by Dave Rand, updated by a couple of other people (see file pred.c) double/mkdble.c100644 0 0 13703 5575033545 12050 0ustar rootroot /* double/mkdble.c create DouBle device/file 24 Dec 1993 * * Copyright (C) 1994 Jean-Marc Verbavatz * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2 of the License, or * (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */ #include #include #include #include #include #include extern int fd; struct stat stbuf; char buffer[DB_MAXSZ]; extern struct db_header dbh; struct dble_device db; /* Find number of blocks of size "size" needed to store "total" bytes */ long get_size(long total, int size) { int l; l = total/size; if(total%size) l++; return l; } main (argc, argv) int argc; char **argv; { char *dev; struct BAT *b; int i,j; u_long size = 0, atol(); float factor, atof(); dbh.magic = DB_MAGIC; /* Default values */ factor = 2.0; db.isize = BLOCK_SIZE; db.osize = DB_MAXSZ; db.iblocks = db.oblocks = 0; db.code = 10; /* Default compression is predictor */ if(argc < 3 || argc > 7) usage(argv[0]); dev = argv[1]; size = atol(argv[2]); if((fd = open(dev, O_RDWR|O_CREAT|O_TRUNC, S_IRUSR| S_IWUSR))<0) usage(argv[0]); if(size < 10) usage(argv[0]); /* is it a joke ? */ if(argc>3) factor = atof(argv[3]); if(argc>4) db.code = atoi(argv[4]); if(argc>5) db.isize = atoi(argv[5]); if(argc>6) db.osize = atoi(argv[6]); if(factor<1 || factor>10) usage(argv[0]); if(db.code && db.code < 101 && db.code > 199 && db.code != 1 && db.code != 212 && db.code != 312 && db.code != 10) usage(argv[0]); if(db.isize < 256 || db.isize>BLOCK_SIZE) usage(argv[0]); if(db.osizeDB_MAXSZ) usage(argv[0]); for(i = db.isize; !(i&1); i>>=1); if(i!=1) { fprintf(stderr,"Block size must be a power of 2\n"); usage(argv[0]); } if(db.osize%db.isize) { fprintf(stderr,"Cluster size must a multiple of block size\n"); usage(argv[0]); } db.iblocks = size*1024/db.isize; /* including header, bitmap and blockmap */ fstat(fd, &stbuf); db.addr_bitmap = 1; if(S_ISREG(stbuf.st_mode)) { if(!(i = stbuf.st_blksize)) i = BLOCK_SIZE; size = get_size(db.iblocks*db.isize, i); /* First iblock of bmap is kept in memory, not written to disk */ db.addr_bitmap += get_size(size*sizeof(u_long), db.isize) - 1; } size = get_size(db.iblocks, 8); /* Bytes bitmap */ db.addr_BAT = db.addr_bitmap + get_size(size, db.isize); db.ratio = db.osize/db.isize; db.BATsize = sizeof(struct BAT)+sizeof(u_long)*(db.ratio-1); i = db.addr_BAT+1; do { db.addr_blocks = i; db.oblocks=(db.iblocks-i)*factor/db.ratio; i=db.addr_BAT+ get_size(db.oblocks, db.isize/db.BATsize); } while(abs(i-db.addr_blocks)>1); db.addr_blocks = i; db.bitmap = malloc(db.isize); db.bitmap_mod = 0; db.bitmap_pos = -1; if(db.bitmap == NULL) { fprintf(stderr, "\n Memory allocation error\n"); exit(1); } dbh.iblocks = db.iblocks; dbh.oblocks = db.oblocks; dbh.isize = db.isize; dbh.osize = db.osize; dbh.addr_bitmap = db.addr_bitmap; dbh.addr_BAT = db.addr_BAT; dbh.addr_blocks = db.addr_blocks; dbh.BATsize = db.BATsize; dbh.ratio = db.ratio; dbh.version = 0x0002; dbh.code = db.code; memset(buffer, 0, db.isize); memcpy(buffer, &dbh, sizeof(dbh)); /* Write header */ if(!db_rw_iblock(&db, WRITE, 0L, buffer)) { fprintf(stderr, "\n Creation error\n"); exit(1); } /* Create bmap && bitmap (not up to date yet) */ memset(buffer, 0, db.isize); for(size = 1; size < db.addr_BAT; size++) { if(!db_rw_iblock(&db, WRITE, size, buffer)) { fprintf(stderr, "\n Creation error\n"); exit(1); } if(!(size&0x7f)) putchar('.'), fflush(stdout); } /* Write empty BAT */ for(i = 0; i < (db.isize/db.BATsize); i++) { b = (struct BAT *)(buffer+i*db.BATsize); b->type = -1; } for(; size= 0) db_rw_iblock(&db, WRITE, db.addr_bitmap+db.bitmap_pos, db.bitmap); /* create other iblocks */ memset(buffer, 0, db.isize); for(size = db.addr_blocks; size < db.iblocks; size++) { db_rw_iblock(&db, WRITE, size, buffer); if(!(size&0x7f)) putchar('.'), fflush(stdout); } putchar('\n'); size = db.oblocks*db.osize; db_close(); printf("%ld clusters of %d bytes (%ld K) compression=%2.2f, granularity=%2.1f%%\n", db.oblocks, db.osize, size/1024, ((float) size)/((db.iblocks-db.addr_blocks)*db.isize), ((float) db.isize)/db.osize*100); printf("Creation Complete\n\n"); } usage(s) char *s; { fprintf(stderr, "\n%s file/device size [factor] [encoding] [block size] [cluster size]\n", s); fprintf(stderr, "\tsize: device size in Kb\n"); fprintf(stderr, "\tfactor: minimum average compression factor.\n"); fprintf(stderr, "\tblock size: [256-%d]\n", BLOCK_SIZE); fprintf(stderr, "\tcluster size: [block size-%d]\n", DB_MAXSZ); fprintf(stderr, "\tencoding: default compression algorithm:\n"); fprintf(stderr, "\t\t0: no encoding\n"); fprintf(stderr, "\t\t1: LZW\n"); fprintf(stderr, "\t\t10: predictor algorithm (default)\n"); fprintf(stderr, "\t\t102: LZV\n"); fprintf(stderr, "\t\t212: LZRW2\n"); fprintf(stderr, "\t\t312: LZRW3A\n"); fprintf(stderr, "\t(No compression can be achieved unless cluster size > block size).\n"); exit(1); } double/HINTS100644 0 0 13210 5575064642 11251 0ustar rootrootHINTS for the DouBle device driver 26 Feb 1994 ---------------------------------- Default Values -------------- These are the default values used by mkdble: compression factor: 2.0 clusters: 10240 bytes blocks: 512 bytes compression: predictor (code 10) Default block and cluster size are only a speed/compression compromise. Speed can be increased by using block size = 1024, compression can be increased by using a block size of 256. In most cases, the cluster size should have little effect on speed and thus the bigger, the better. 10240 is currently the maximum. Note: the cluster size has no influence on filesystem block size. I know it might be confusing, but you should not be tempted to reduce its size for a filesystem containing small files. You may want to decrease the cluster size if you are going to do mainly random access. Data security issues -------------------- The most important thing with a compressed device is to never, never, let it run out of space. In that purpose: - Do not overfill it. - Do not store compressed files on it. - Choose an appropriate compression factor and algorithm when creating the device. The driver recovers very poorly from errors resulting from running out of space. Do not store data on a compressed device unless you fully understand that it might be lost. BTW the driver is still ALPHA code. run dbck (df is easier if you are using mount -t dble ...) frequently, to make sure that the compressed device is not full. The default compression factor of 2.0 is, in most cases, too high ----------------------------------------------------------------- It is recommended to use a value SMALLER than the average compression factor expected from the data and from the compression method used. There is currently no other mean to measure the compression factor than trial and error. This is what I recommend: - Make a device with a compression factor of 1.6. - Start using it and after some time, use dbck to see what compression was achieved. If it is less than 1.6, make it again. If it is more than 1.7, you can make it again as well, but it is safe to work with 1.6. The default algorithm is not the best compressor ------------------------------------------------ The predictor algorithm (default) is in the public domain. It is used in PPP. As it is not the case of other algorithms included, I will try in future release to make it work better. According to benchmarks I have done, this is how the algorithms included compare (as far as compression goes): best - LZW = LZV >= LZRW3A > LZRW2 > PREDICTOR - worst Note: Before choosing the algorithm you want to use, have a look at the speed comparison. It is easy to make a DouBle device use a different algorithm (see mkdble arguments) and the default value can also be changed in mkdble.c (search for predictor and change code 10 with 212 or 312). DBLE_FS option -------------- With the DBLE_FS option set, DouBle devices can be put in /etc/fstab. As an example this is an excerpt of my fstab file: /dev/hdb1 / ext2 defaults,remount 0 1 /dev/hdb2 /dev/cdble2 dble defaults /dev/dble2 /home ext2 defaults The "dble" entry MUST preceed the filesystem entry that uses it. This is an excerpt of my /etc/rc file: #!/bin/sh # check fs before mounting # dbmount /dev/hdb2, so that the filesystem on it be checked dbmount /dev/hdb2 /dev/dble2 fsck -A -av # dbumount /dev/dble2, so that it can be mounted with mount dbumount /dev/dble2 # (re)mount filesystems including root mount -nav # root is now r/w # remove /etc/mtab* so mount creates the /etc/mtab file /bin/rm -f /etc/mtab* # write /etc/mtab (fake mount to update /etc/mtab) /etc/mount -fa As the dbck utility is not to fsck standards yet, it is recommended to link /bin/true to /etc/fs/fsck.dble. Speed considerations -------------------- Access to a compressed device is slower than to a normal block device. The purpose of this driver is to transparently make more disk space available. However, there are ways to increase speed. This one hold even without the driver. Recently, several patches have been done to improve disk access. The cluster patches now have been incorporated into the kernel. For IDE disks, the IDE performance patches may help. I've been using them with double-0.2b without problem. Because the default block size under Linux is 1024 bytes, compressed devices with a block size of 1024 are faster. The default value of 512 bytes emphasizes compression. Buffer caches within the driver will compensate for speed differences due to block size. For better performance, the number of internal buffers (particularly DB_NR_BH in linux/include/linux/double.h) can be increased. Unfortunately, the driver buffers are independent from kernel buffers and need to be permanently allocated. Block devices are faster than regular files used as compressed devices. The reason is that any read/write operation on a regular file goes through additional layers. Finally, speed is also dependent on the compression algorithm used. According to benchmark I have done: fastest - LZRW2 > LZV > PREDICTOR > LZRW3A >> LZW - slowest LZW is particulary slow in reading. Note: the speed of the predictor algorithm has been improved, by Peter Trattler, since these tests. FINAL REMARKS ------------- If you have suggestions or problems, feel free to get in touch with me, either by e-mail or through the COMPRESSION channel on niksula.hut.fi. Please report possible bugs as soon as possible. In case of data loss with a given compression algorithm, I suggest you try another one and then tell me if you had the problem with both, or only one of them. Thank you for using the DouBle device driver; compress safely ! Good Luck, Jean-Marc Verbavatz double/mount.c100644 0 0 25410 5533704557 11754 0ustar rootroot/* mount.c - A better mount command for Linux 0.99-patchlevel 8 or later. by Peter Orbaek Copyright (C) 1992,93 Peter Orbaek. This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */ #define _BSD_SOURCE #define _POSIX_SOURCE #include #include #include #include #include #include #include #include #include #include /*#define _LINUX_TYPES_H*/ #include /* these really should be defined in . */ #define MNTOPT_NODEV "nodev" #define MNTOPT_NOEXEC "noexec" #define MNTOPT_SYNC "sync" #define MNTOPT_REMOUNT "remount" #ifndef __STDC__ #error Error: This program requires ANSI C to compile #endif #define MTAB_FILE MOUNTED #define LOCK_FILE "/etc/mtab~" #define FSTAB MNTTAB #define UFSTAB "/etc/ufstab" int opt_mountall = 0; int opt_print = 0; int opt_verbose = 0; int opt_std = 0; int opt_usermount= 0; int opt_fakemtab = 0; int opt_nomtab = 0; int opt_noauto = 0; char opt_nostd[200]; char mntoptions[200] = "defaults"; char mnttype[MNTMAXSTR] = ""; char *mntdev = NULL, *mntdir = NULL; char mntdevbuf[MNTMAXSTR]; void usage(), process_options(char *opts); void err(char *str); void print_mtab(char *); int do_mount(struct mntent *); int lock_mtab(); void unlock_mtab(); void print_mntent(struct mntent *); void usage() { fprintf(stderr, "Usage: mount [-afnpruv] [-t type] [-o options] [[dev] dir]\n"); err(NULL); } int main(int argc, char *argv[]) { char c; /* parse options */ while((c = getopt(argc, argv, "afnput:rvo:")) != EOF) { switch(c) { case 'a': opt_mountall = 1; break; case 'p': opt_print = 1; break; case 't': strncpy(mnttype, optarg, MNTMAXSTR-1); break; case 'r': if(mntoptions[0] != '\0') strcat(mntoptions, ","); strcat(mntoptions, "ro"); break; case 'v': opt_verbose = 1; break; case 'o': strncpy(mntoptions, optarg, sizeof(mntoptions)-1); break; case 'u': opt_usermount = 1; break; case 'f': opt_fakemtab = 1; break; case 'n': opt_nomtab = 1; break; default: usage(); } } if(getuid()) opt_usermount = 1; if(optind < argc) { mntdev = argv[optind++]; if(optind >= argc) { char *filename = opt_usermount ? UFSTAB : FSTAB; FILE *fstab; struct mntent *mp; /* only a mount-point was given, look up device in fstab */ mntdir = mntdev; mntdev = NULL; if(!(fstab = setmntent(filename, "r"))) err(filename); while((mp = getmntent(fstab))) { if(!strcmp(mntdir, mp->mnt_dir)) { strncpy(mntdevbuf, mp->mnt_fsname, sizeof(mntdevbuf)-1); mntdev = mntdevbuf; if ( !mnttype[0] ) strncpy(mnttype, mp->mnt_type, sizeof(mnttype)-1); break; } else if(!strcmp(mntdir, mp->mnt_fsname)) { strncpy(mntdevbuf, mp->mnt_dir, sizeof(mntdevbuf)-1); mntdev = mntdir; mntdir = mntdevbuf; if ( !mnttype[0] ) strncpy(mnttype, mp->mnt_type, sizeof(mnttype)-1); } } endmntent(fstab); /* * If the fstab lookup failed, maybe it's a filesystem that's * already been mounted, in which case the "remount" option has * to be set. We process the options early to test this. */ process_options ( mntoptions ); if (!mntdev && (opt_std & MS_REMOUNT)) { if(!(fstab = setmntent(MTAB_FILE, "r"))) err(filename); while((mp = getmntent(fstab))) { if(!strcmp(mntdir, mp->mnt_dir)) { strncpy(mntdevbuf, mp->mnt_fsname, sizeof(mntdevbuf)-1); mntdev = mntdevbuf; break; } else if(!strcmp(mntdir, mp->mnt_fsname)) { strncpy(mntdevbuf, mp->mnt_dir, sizeof(mntdevbuf)-1); mntdev = mntdir; mntdir = mntdevbuf; } } } if(!mntdev) { fprintf(stderr, "mount: Don't know what to mount on %s\n", mntdir); err(NULL); } } else mntdir = argv[optind]; } else if(argc == 1) { /* with no args, just print mtab */ print_mtab(MTAB_FILE); unlock_mtab(); exit(0); } /* done with the arguments, now do some work */ if(geteuid()) { fprintf(stderr, "mount: You must be root to mount a filesystem.\n"); err(NULL); } /* check for lock */ if(!opt_nomtab && !lock_mtab()) { /* don't use err() for this */ fprintf(stderr, "mount: A lock-file exists, mount denied.\n"); exit(1); } if(opt_mountall) { /* read the /etc/fstab or /etc/ufstab and mount the filesystems */ char *filename = opt_usermount ? UFSTAB : FSTAB; FILE *fstab; struct mntent *mp; if(!(fstab = setmntent(filename, "r"))) err(filename); while((mp = getmntent(fstab))) { if(mnttype[0] == '\0' || !strcmp(mnttype, mp->mnt_type)) { if(opt_usermount && (mp->mnt_opts == NULL || mp->mnt_opts[0] == '\0')) { mp->mnt_opts = "ro,nosuid,noexec,nodev"; } if(opt_print) print_mntent(mp); else (void) do_mount(mp); } } endmntent(fstab); } else if(mntdir) { struct mntent mnt; if(opt_usermount) { FILE *fstab; struct mntent *mp; int flag = 0; if(!(fstab = setmntent(UFSTAB, "r"))) err(UFSTAB); while((mp = getmntent(fstab))) { if(!strcmp(mntdev, mp->mnt_fsname) && !strcmp(mntdir, mp->mnt_dir)) { flag = 1; strncpy(mntoptions, mp->mnt_opts, sizeof(mntoptions)-1); strncpy(mnttype, mp->mnt_type, sizeof(mnttype)-1); break; } } endmntent(fstab); if(!flag) { fprintf(stderr, "mount: Can't usermount %s.\n", mntdir); err(NULL); } } mnt.mnt_type = mnttype; mnt.mnt_fsname = mntdev; mnt.mnt_dir = mntdir; mnt.mnt_opts = mntoptions; mnt.mnt_freq = 0; mnt.mnt_passno = 0; if(!do_mount(&mnt)) { unlock_mtab(); exit(1); } } unlock_mtab(); exit(0); } int lock_mtab() { int fd; if((fd = open(LOCK_FILE, O_WRONLY | O_CREAT | O_EXCL, 0744)) < 0) return 0; close(fd); return 1; } void unlock_mtab() { unlink(LOCK_FILE); } int do_mount(struct mntent *mp) { struct stat s; FILE *mtab; if(!mp->mnt_type || !mp->mnt_type[0]) mp->mnt_type = "minix"; process_options(mp->mnt_opts); if ( opt_mountall && opt_noauto ) return 0; if(!opt_fakemtab) { /* Swap is not mounted on a directory JMV */ if(strcmp(mp->mnt_type, MNTTYPE_SWAP) == 0) { if(swapon(mp->mnt_fsname) < 0) { fprintf(stderr, "mount: swapon(%s) failed: %s\n", mp->mnt_fsname, strerror(errno)); return 0; } if(opt_verbose) fprintf(stderr, "Added swap: %s\n", mp->mnt_fsname); return 1; } /* check the directory */ if(stat(mp->mnt_dir, &s) < 0) { if(errno == ENOENT || errno == ESRCH) { if(mkdir(mp->mnt_dir, 0755) < 0) { fprintf(stderr, "mount: mkdir(%s) failed.\n", mp->mnt_dir); return 0; } if(opt_verbose) fprintf(stderr, "Made directory: %s\n", mp->mnt_dir); } else { fprintf(stderr, "mount: stat(%s) failed.\n", mp->mnt_dir); return 0; } } #if 0 else if(!S_ISDIR(s.st_mode)) { fprintf(stderr, "mount: %s already exists, and isn't a directory.\n", mp->mnt_dir); return 0; } #endif #if 0 printf("mount(%s,%s,%s,%x,%s)\n", mp->mnt_fsname, mp->mnt_dir, mp->mnt_type, opt_std, opt_nostd); #endif if(strcmp(mp->mnt_dir, "/") == 0 && !(opt_std & MS_REMOUNT)) { if(opt_verbose) fprintf(stderr, "mount: root already mounted by kernel\n"); } else { if(strcmp(mp->mnt_type, MNTTYPE_IGNORE) == 0) { if(opt_verbose) fprintf(stderr, "mount: ignored %s\n", mp->mnt_fsname); return 1; } if(mount(mp->mnt_fsname, mp->mnt_dir, mp->mnt_type, 0xc0ed0000|opt_std, opt_nostd) < 0) { fprintf(stderr, "mount: mount(%s,%s) failed: %s\n", mp->mnt_fsname, mp->mnt_dir, strerror(errno)); return 0; } if(opt_verbose) fprintf(stderr, "Mounted %s on %s.\n", mp->mnt_fsname, mp->mnt_dir); } } /* if(!opt_fakemtab) */ /* swap fs should not appear in MTAB JMV */ /* MTAB should be updated when remounting root from read-only */ if(!opt_nomtab && (!(opt_std & MS_REMOUNT) || !strcmp(mp->mnt_dir, "/")) && strcmp(mp->mnt_type, MNTTYPE_SWAP)) { if(!(mtab = setmntent(MTAB_FILE, "a"))) { fprintf(stderr, "mount: open(%s) failed.\n", MTAB_FILE); return 1; } addmntent(mtab, mp); endmntent(mtab); } return 1; } void err(char *str) { if(str) fprintf(stderr, "mount: %s: %s\n", str, strerror(errno)); if(access(LOCK_FILE, 0) == 0) unlink(LOCK_FILE); exit(1); } void print_mntent(struct mntent *mp) { printf("%s\t%s\t%s\t%s\t%d\t%d\n", mp->mnt_fsname, mp->mnt_dir, mp->mnt_type, (mp->mnt_opts[0] == 0) ? "defaults" : mp->mnt_opts, mp->mnt_freq, mp->mnt_passno); } void print_mtab(char *filename) { FILE *mf; struct mntent *mp; if(!((mf = setmntent(filename, "r")))) err(filename); while((mp = getmntent(mf))) print_mntent(mp); endmntent(mf); } void process_options(char *opts) { /* opts is a comma-separated list of options */ char opt[MNTMAXSTR]; char *p; opt_nostd[0] = '\0'; opt_std = 0; opt_noauto = 0; while(opts && *opts) { for(p = opt; *opts && *opts != ','; *p++ = *opts++); *p = '\0'; if(*opts == ',') opts++; /* standard options, should be supported by all filesystems */ if(!strcmp(opt, MNTOPT_DEFAULTS)) { if(opt_usermount) opt_std = MS_NOSUID|MS_NODEV|MS_RDONLY|MS_NOEXEC; else opt_std = 0; } else if(!strcmp(opt, MNTOPT_RO)) opt_std |= MS_RDONLY; else if(!strcmp(opt, MNTOPT_RW)) opt_std &= ~MS_RDONLY; else if(!strcmp(opt, MNTOPT_SUID)) opt_std &= ~MS_NOSUID; else if(!strcmp(opt, MNTOPT_NOSUID)) opt_std |= MS_NOSUID; else if(!strcmp(opt, MNTOPT_NODEV)) opt_std |= MS_NODEV; else if(!strcmp(opt, MNTOPT_NOEXEC)) opt_std |= MS_NOEXEC; else if(!strcmp(opt, MNTOPT_SYNC)) opt_std |= MS_SYNC; else if(!strcmp(opt, MNTOPT_REMOUNT)) opt_std |= MS_REMOUNT; /* * Not a *real* mount option, but a directive to us which is * ignored if -a wasn't specified. */ else if(!strcmp(opt, MNTOPT_NOAUTO)) opt_noauto = 1; else { /* non-standard options are put in a comma-sep. string */ strcat(opt_nostd, opt); strcat(opt_nostd, ","); } } if(opt_nostd[0]) opt_nostd[strlen(opt_nostd)-1] = '\0'; } double/mount.diff100644 0 0 617 5533704666 12405 0ustar rootroot--- mount.c~ Sat Feb 19 16:37:47 1994 +++ mount.c Sat Feb 19 16:42:45 1994 @@ -319,11 +319,14 @@ return 0; } - } else if(!S_ISDIR(s.st_mode)) { + } +#if 0 + else if(!S_ISDIR(s.st_mode)) { fprintf(stderr, "mount: %s already exists, and isn't a directory.\n", mp->mnt_dir); return 0; } +#endif #if 0 printf("mount(%s,%s,%s,%x,%s)\n", mp->mnt_fsname, mp->mnt_dir, double/dbmode.c100600 0 0 6702 5572605616 12016 0ustar rootroot/* double/dbmode.c changes compression algorithm of DouBle file * 8 Mar 1994 * Copyright (C) 1994 Jean-Marc Verbavatz * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2 of the License, or * (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */ #include #include #include #include #include struct dble_device db; struct dble_info info; extern struct db_header dbh; extern int fd; int permanent = 0; void read_opt(char *name, char *s) { while(*s) { switch(*s) { case 'p': permanent = 1; break; case 0: return; default: usage(name); } s++; } } main(argc, argv) int argc; char **argv; { char *file = NULL; struct stat statbuf; int i, mode = -1; for(i = 1; i < argc; i++) switch(*argv[i]) { case '-': read_opt(argv[0], argv[i]+1); break; default: if(file == NULL) { file = argv[i]; break; } if(mode == -1) mode = atoi(argv[i]); else mode = -1; if(mode == -1) usage(argv[0]); } if(file == NULL) usage(argv[0]); if(stat(file, &statbuf)<0) usage(argv[0]); if(S_ISREG(statbuf.st_mode) && !permanent) usage(argv[0]); if(permanent) { if(!db_open(&db, file)) usage(argv[0]); printf("DouBle device version %d.%d\n", dbh.version>>8, dbh.version&0xff); if(dbh.version < 2 && mode == -1) printf("Old device; new mode recommended\n"); if(dbh.version > 2) { fprintf(stderr, "Old %s version\n", argv[0]); mode = -1; } printf("Current default compression algorithm: %d\n", dbh.code); switch(mode) { case 10: case 102: case 212: case 312: dbh.version = 2; case 0: case 1: dbh.code = mode; lseek(fd, 0L, 0); write(fd, &dbh, sizeof(dbh)); printf("Algorithm changed to: %d\n", mode); case -1: break; default: fprintf(stderr, "Invalid mode\n"); usage(argv[0]); } db_close(); } else { fd = open(file, O_RDONLY); if(fd < 0) usage(argv[0]); if(ioctl(fd, DBLE_GET_STATUS, &info)) usage(argv[0]); printf("Current compression algorithm: %d\n", info.code); switch(mode) { case 0: case 1: case 10: case 102: case 212: case 312: info.code = mode; ioctl(fd, DBLE_SET_STATUS, &info); printf("Algorithm changed to: %d\n", mode); case -1: break; default: fprintf(stderr, "Invalid mode\n"); usage(argv[0]); } close(fd); } } usage(char *s) { if(errno) perror(s); printf("usage: %s -p device_file [mode]\n", s); printf("\t\tChange default compression algorithm\n"); printf("\t\tOnly use on not mounted device_file\n"); printf("\n %s /dev/double[0-7] [mode]\n", s); printf("\t\tChange current compression algorithm\n"); printf("\t\tOnly use on mounted device_file\n"); printf("\n\tmode:\n"); printf("\t\t0: no compression\n"); printf("\t\t1: LZW (not recommended)\n"); printf("\t\t10: predictor\n"); printf("\t\t102: LZV\n"); printf("\t\t212: LZRW2\n"); printf("\t\t312: LZRW3A\n\n"); exit(1); } double/dbmount.c100644 0 0 2554 5572605640 12242 0ustar rootroot/* double/dbmount.c mount device/file on DouBle device 1 Jan 1994 * * Copyright (C) 1994 Jean-Marc Verbavatz * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2 of the License, or * (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */ #include #include #include #include #include main(argc, argv) int argc; char **argv; { int fd, gd; if(argc != 3 || (fd = open(argv[1], O_RDWR))<0 || (gd = open(argv[2], O_RDWR)) < 0) { if(errno) perror(argv[0]); usage(argv[0]); } if(ioctl(gd, DBLE_SET_FD, fd)) if(errno) perror(argv[0]); close(gd); close(fd); } usage(s) char *s; { fprintf(stderr, "\nusage: %s file/dev /dev/double[0-7]\n", s); fprintf(stderr, "\tmount file/dev on DouBle device\n"); exit(-1); } double/dbumount.c100644 0 0 2462 5572605677 12437 0ustar rootroot/* double/dbumount.c umount device/file from DouBle device 1 Jan 1994 * * Copyright (C) 1994 Jean-Marc Verbavatz * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2 of the License, or * (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */ #include #include #include #include #include main(argc, argv) int argc; char **argv; { int fd; if(argc != 2 || (fd = open(argv[1], O_RDWR))<0) { if(errno) perror(argv[0]); usage(argv[0]); } if(ioctl(fd, DBLE_CLR_FD)) if(errno) perror(argv[0]); close(fd); } usage(s) char *s; { fprintf(stderr, "\nusage: %s /dev/double[0-7]\n", s); fprintf(stderr, "\tdemount file/dev from DouBle device\n"); exit(-1); } double/README.dbmode100600 0 0 2324 5544171610 12514 0ustar rootrootdbmode: changes default or current compression algorithms, and updates headers to version 0.2 USAGE ----- First, read the WARNING section down below. - The default compression algorithm is the value that was used at creation. It is permanently stored in the device_file header. - The current compression algorithm is the value currently being used. It is reset to the default value at each mount. dbmode has 2 forms: - with the "-p" option, you need to specifiy the name of a device/file, which must not be mounted. This is to change the default value. If changing from version 0.1, it is highly recommended to use "312" (lzrw3a). The other algorithms will not yield the same compression as LZW and therefore cause problems. - without the "-p" option, you are dealing with the current algorithm, and the first argument is the /dev/double[0-7]. In both forms, the second argument [mode] is optional. If not present, dbmode will just display current values. If using -p option with one of the new version 0.2 algorithms, the file header will magically be updated to version 0.2 (I hope). WARNINGS -------- - This program has not been tested. - This program does not change the size of blocks, clusters or the compression factor. double/lzv.c120777 0 0 0 5554510512 17654 2/usr/src/linux/drivers/block/lzv.custar rootrootdouble/lzw.c120777 0 0 0 5554510512 17656 2/usr/src/linux/drivers/block/lzw.custar rootrootdouble/lzrw2.c120777 0 0 0 5554510512 20366 2/usr/src/linux/drivers/block/lzrw2.custar rootrootdouble/lzrw3-a.c120777 0 0 0 5554510512 21024 2/usr/src/linux/drivers/block/lzrw3-a.custar rootrootdouble/lzrw.h120777 0 0 0 5554510512 20234 2/usr/src/linux/drivers/block/lzrw.hustar rootrootdouble/double-0.2b.patch100644 0 0 446607 5575062235 13433 0ustar rootroot--- linux/fs/super.c~ Thu May 26 03:19:37 1994 +++ linux/fs/super.c Tue May 31 15:22:49 1994 @@ -27,6 +27,7 @@ extern void wait_for_keypress(void); extern void fcntl_init_locks(void); +extern int dble_may_umount(dev_t); extern int root_mountflags; @@ -391,6 +392,39 @@ if (retval) return retval; } +#ifdef CONFIG_DBLE_FS +/* is that a double device inode ? + * If so, inode points to the double device inode (BLOCK), + * s_covered points to the device_file (BLOCK or REG) and + * s_mounted points to the double device (BLOCK). + * in addition, the first mounted double device has minor > 128 + * For a normal mount entry, s_mounted is the root directory entry + * on the block device and s_covered is the directory entry on the root fs, + * where the fs is mounted. + */ + if(S_ISBLK(inode->i_mode) && (inode->i_rdev&0x80) && + get_super(inode->i_rdev) == inode->i_sb && + !S_ISDIR(inode->i_sb->s_mounted->i_mode)) { + /* Not mounted on a directory; must be a double device */ + struct super_block *sb; + + dev = inode->i_rdev; + sb = inode->i_sb; + iput(inode); + if (!sb->s_covered) + return -ENOENT; + if(!dble_may_umount(dev)) + return -EBUSY; + /* Now, clean kernel buffers */ + sb->s_covered->i_mount = NULL; + iput(sb->s_mounted); /* Double device */ + sb->s_mounted = NULL; + sb->s_covered = NULL; /* device file */ + /* close device; will also flush buffers and iput(device file) */ + put_super(dev); + return 0; + } +#endif if (S_ISBLK(inode->i_mode)) { dev = inode->i_rdev; if (IS_NODEV(inode)) { @@ -509,7 +543,7 @@ return retval; } -static int copy_mount_options (const void * data, unsigned long *where) +static int copy_mount_options (char * data, unsigned long *where) { int i; unsigned long page; @@ -558,6 +592,7 @@ { struct file_system_type * fstype; struct inode * inode; + struct inode * dinode; struct file_operations * fops; dev_t dev; int retval; @@ -586,6 +621,76 @@ if (!fstype) return -ENODEV; t = fstype->name; +#ifdef CONFIG_DBLE_FS + if(!strcmp(t, "dble")) { +/* Here, we essentially copy dir_name inode into data and mount. + * This is all done here because do_mount will only take a directory. + * Otherwise, it is quite similar to normal mounts. + */ + struct super_block *sb; + + /* First, try to open device/file */ + retval = namei(dev_name, &inode); + if(retval) + return retval; + if (inode->i_count != 1 || inode->i_mount) { + iput(inode); + return -EBUSY; + } + if(S_ISBLK(inode->i_mode)) { /* Need to open ? */ + if (IS_NODEV(inode)) { + iput(inode); + return -EACCES; + } + dev = inode->i_rdev; + if (MAJOR(dev) >= MAX_BLKDEV) { + iput(inode); + return -ENXIO; + } + fops = get_blkfops(MAJOR(dev)); + if (fops && fops->open) { + retval = fops->open(inode,NULL); + if (retval) { + iput(inode); + return retval; + } + } + check_disk_change(dev); + } + /* Now, try to open double device */ + retval = namei(dir_name, &dinode); + if(retval) { + iput(inode); + return retval; + } + if(!S_ISBLK(dinode->i_mode)) { + iput(inode); + iput(dinode); + return -ENOTBLK; + } + /* The device used for mounting "dble" must be block and >128 */ + dev = dinode->i_rdev; + if(!(dev&0x80)) { + iput(inode); + iput(dinode); + return -EINVAL; + } +/* Each mtab entry has a superblock, and double devices are mounted twice. + */ + /* Call double driver with inode of device file in data */ + flags = new_flags & ~MS_MGC_MSK; + sb = read_super(dev, t, flags, (void *)inode, 0); + if (!sb) { + iput(dinode); + iput(inode); + return -EBUSY; + } + dinode->i_sb = sb; + sb->s_covered = inode; + inode->i_mount = sb->s_mounted = dinode; + return 0; + } +#endif if (fstype->requires_dev) { retval = namei(dev_name,&inode); if (retval) --- linux/fs/filesystems.c~ Thu May 26 03:19:38 1994 +++ linux/fs/filesystems.c Tue May 31 15:22:49 1994 @@ -19,6 +19,7 @@ #include #include #include +#include extern void device_setup(void); @@ -89,6 +90,10 @@ {hpfs_read_super, "hpfs", 1, NULL}); #endif +#ifdef CONFIG_DBLE_FS + register_filesystem(&(struct file_system_type) + {dble_read_super, "dble", 0, NULL}); +#endif mount_root(); return 0; } --- linux/include/linux/double.h~ Tue May 31 15:22:50 1994 +++ linux/include/linux/double.h Tue Jun 7 10:56:06 1994 @@ -0,0 +1,125 @@ +/* + * linux/include/linux/double.h + * + * configuration for the double disk compression driver + * + * Copyright (C) 1994 Jean-Marc Verbavatz + * January 1994 + */ +#include + +#define DB_MAGIC 91262 /* An anniversary */ +#define DB_MAXSZ 10240 /* Max size of clusters */ +#define MAJOR_NR 19 /* Was unused */ +#define MAX_DBLE 8 /* Max # of devices */ +#define DB_NR_BH 36 /* # of disk buffer_heads */ +#define DB_NR_VB 4 /* # of memory clusters */ +#define DB_BMAP 1 /* For regular files */ +/* + * IOCTL's + */ +#define DBLE_SET_FD 0x4400 /* for dbmount */ +#define DBLE_CLR_FD 0x4401 /* for dbumount */ +#define DBLE_SET_STATUS 0x4402 /* Change parameters */ +#define DBLE_GET_STATUS 0x4403 /* Get parameters */ +#define DBLE_FLUSH 0x4404 /* Flush buffers */ +#define DBLE_DEBUG 0x4405 /* Change debug mode */ +#define DBLE_STAT 0x4406 /* For performance study */ + +typedef u_char byte; /* Both types for lzw.c */ +typedef u_short code; + +/* Cluster structure */ + +struct v_buffer { + long block; + struct dble_device *db; + u_char db_dev; + u_char clean; /* 0 is empty, 1 is uptodate, 2 is dirty */ + char data[DB_MAXSZ]; +}; + +/* Block Allocation Table: each cluster is made of several physical + * blocks (iblocks) + */ +struct BAT { + short type; /* Compression mode */ + u_long iblock; /* physical blocks for cluster */ + /* other blocks are allocated dynamically (depending on ratio) */ +}; + +/* Disk header created by mkdble */ +extern struct db_header { + int magic; + u_long iblocks, oblocks; /* size of physical/virtual devices */ +/* block number of bitmap, BAT and available blocks */ + u_long addr_bitmap, addr_BAT, addr_blocks; + u_short isize, osize; /* size blocks/clusters in bytes */ + int BATsize; /* size of struct BAT */ + int ratio; /* osize/isize */ + int version; /* Driver version */ + short code; /* Default coding technique */ +} db_header; + +/* run-time structure for device */ +struct dble_device { + u_long iblocks, oblocks; + u_long addr_bitmap, addr_BAT, addr_blocks; + long bitmap_pos, BAT_pos; /* block currently loaded */ + long first_free; /* Where there was free blocks */ + struct inode *db_inode; /* inode of physical device */ + dev_t db_device; /* physical device */ + int db_flags; /* physical file mode */ + int db_refcnt; /* number of opens */ +/* Memory buffers : */ + u_char *bitmap, *BAT_block; + long *bmap0; + u_short isize, osize; + int BATsize; + int ratio; + u_short code; /* Compression mode */ + u_char bitmap_mod, BAT_mod; /* uptodate ?? */ + u_char db_number; + u_char db_mounted; + u_char debug; /* debug mode */ +}; + +/* SET/GET status structure */ +struct dble_info { + dev_t db_device; /* GET status only */ + dev_t db_rdevice; /* GET status only */ + u_long db_inode; /* GET only */ + int db_flags; /* GET only */ + u_long iblocks, oblocks; /* GET only */ + u_short isize, osize; /* GET only */ + u_char code; /* Compression method */ +}; + +struct db_stat { + long rphysical, rvirtual; + long wphysical, wvirtual; + long ihit, inohit; + long ohit, onohit; + long roblock, woblock; +} dble_stat; + +extern struct buffer_head **db_bh; + +extern u_long get_newbit(struct dble_device *); +extern int WLZW(byte *, code *, int, int); +extern int RLZW(code *, byte *, int len); +extern int wLZV(void *, void *, int, int *); +extern int rLZV(void *, void *, int len); +extern void wlzrw2(byte *, int len, byte *, int *); +extern int rlzrw2(byte *, byte *, int); +extern int rpred(byte *, byte *, int); +extern void wpred(byte *, int, byte *, int *); +extern void wlzrw3a(byte *, int, byte *, int *); +extern int rlzrw3a(byte *, byte *, int); +extern void wlzrw3(byte *, int, byte *, int *); +extern int rlzrw3(byte *, byte *, int); +extern int db_rw_iblock(struct dble_device *, int, long, u_char *); +extern int read_cluster(struct v_buffer *); +extern int write_cluster(struct v_buffer *); +extern int db_rheader(struct dble_device *); +extern int db_flush(struct dble_device *, int); --- linux/include/linux/fs.h~ Tue May 31 15:29:08 1994 +++ linux/include/linux/fs.h Mon Jun 6 17:07:28 1994 @@ -251,6 +251,7 @@ #include #include #include +#include struct super_block { dev_t s_dev; @@ -276,6 +277,7 @@ struct nfs_sb_info nfs_sb; struct xiafs_sb_info xiafs_sb; struct sysv_sb_info sysv_sb; + struct dble_sb_info dble_sb; void *generic_sbp; } u; }; --- linux/include/linux/major.h~ Thu May 26 03:19:41 1994 +++ linux/include/linux/major.h Tue May 31 15:22:51 1994 @@ -66,7 +66,8 @@ #define SOCKET_MAJOR 16 #define AF_UNIX_MAJOR 17 #define AF_INET_MAJOR 18 -/* unused: 19, 20 */ +#define DBLE_MAJOR 19 +/* unused: 20 */ #define SCSI_GENERIC_MAJOR 21 /* unused: 22 */ #define MITSUMI_CDROM_MAJOR 23 --- linux/include/linux/double_fs.h~ Tue May 31 15:22:51 1994 +++ linux/include/linux/double_fs.h Tue May 31 15:22:51 1994 @@ -0,0 +1,16 @@ +#ifndef LINUX_DBLE_FS_H +#define LINUX_DBLE_FS_H + +/* + * Definitions for DouBle device pseudo filesystems + * + * Copyright (C) 1994, Jean-Marc Verbavatz + * + * Feb 1994 + */ + +#define DBLE_SUPER_MAGIC 0x91262 + +extern struct super_block *dble_read_super(struct super_block *, struct inode *, int); + +#endif --- linux/include/linux/double_fs_sb.h~ Tue May 31 15:22:51 1994 +++ linux/include/linux/double_fs_sb.h Tue May 31 15:22:51 1994 @@ -0,0 +1,9 @@ +/* + * DouBle device super block info + * + * Jean-Marc Verbavatz, Feb 1994 + */ + +struct dble_sb_info { + void *db; /* actually struct dble_device * */ +}; --- linux/drivers/block/lzrw.h~ Tue May 31 15:22:51 1994 +++ linux/drivers/block/lzrw.h Tue May 31 15:22:51 1994 @@ -0,0 +1,101 @@ +/* Author : Ross Williams. */ +/* Date : December 1989. */ +/* This header file and the C functions have been modified in order to */ +/* include them in the DouBle device driver by Jean-Marc Verbavatz, Feb 1994. */ +/* */ +/* This header file defines the interface to a set of lzrw functions */ +/* each member of which implements a particular data compression */ +/* algorithm. */ +/* */ +/* Normally in C programming, for each .H file, there is a corresponding .C */ +/* file that implements the functions promised in the .H file. */ +/* Here, there are many .C files corresponding to this header file. */ +/* Each comforming implementation file contains a single function */ +/* called that implements a single data compression */ +/* algorithm that conforms with the interface specified in this header file. */ +/* */ +/******************************************************************************/ +/* See the formal C definition later for a description of the parameters. */ +/* */ +/* Although compression algorithms usually compress data, there will always */ +/* be data that a given compressor will expand (this can be proven). */ +/* */ +/* Unfortunately, in general, the only way to tell if an algorithm will */ +/* expand a particular block of data is to run the algorithm on the data. */ +/* If the algorithm does not continuously monitor how many output bytes it */ +/* has written, it might write an output block far larger than the input */ +/* block before realizing that it has done so. */ +/* On the other hand, continuous checks on output length are inefficient. */ +/* */ +/* The problem does not arise for decompression. */ +/* */ +/******************************************************************************/ +/* Macro definitions and types that are likely to change between computers. */ +/* */ +#ifndef DONE_PORT /* Only do this if not previously done. */ + #ifndef TRUE + #define TRUE 1 + #define FALSE 0 + #endif + #ifndef UBYTE + #define UBYTE unsigned char /* Unsigned byte */ + #define UWORD unsigned short /* Unsigned word (2 bytes) */ + #define ULONG unsigned long /* Unsigned word (4 bytes) */ + #endif + + #define DONE_PORT /* Don't do all this again. */ + #define LOCAL static /* For non-exported routines. */ + #define EXPORT /* Signals exported function. */ + +#endif + + +int rlzrw2( /* function for decompression algorithm. */ +UBYTE *src_adr, /* Address of input data. */ +UBYTE *dst_adr, /* Address of output data. */ +ULONG dst_len /* Length of output data. */ +); + +void wlzrw2( /* function for compression algorithm. */ +UBYTE *src_adr, /* Address of input data. */ +ULONG src_len, /* Length of input data. */ +UBYTE *dst_adr, /* Address of output data. */ +ULONG *p_dst_len /* Pointer to a longword where routine will write: */ + /* Length of output data. */ +); + +int rlzrw3( /* function for decompression algorithm. */ +UBYTE *src_adr, /* Address of input data. */ +UBYTE *dst_adr, /* Address of output data. */ +ULONG dst_len /* Length of output data. */ +); + +void wlzrw3( /* function for compression algorithm. */ +UBYTE *src_adr, /* Address of input data. */ +ULONG src_len, /* Length of input data. */ +UBYTE *dst_adr, /* Address of output data. */ +ULONG *p_dst_len /* Pointer to a longword where routine will write: */ + /* Length of output data. */ +); +/* + * NOTE: lzrw3 is not implemented in the DouBle driver version 0.2 + */ + +int rlzrw3a( /* function for decompression algorithm. */ +UBYTE *src_adr, /* Address of input data. */ +UBYTE *dst_adr, /* Address of output data. */ +ULONG dst_len /* Length of output data. */ +); + +void wlzrw3a( /* function for compression algorithm. */ +UBYTE *src_adr, /* Address of input data. */ +ULONG src_len, /* Length of input data. */ +UBYTE *dst_adr, /* Address of output data. */ +ULONG *p_dst_len /* Pointer to a longword where routine will write: */ + /* Length of output data. */ +); + +/******************************************************************************/ +/* End of LZRW.H */ +/******************************************************************************/ + --- linux/drivers/block/blk.h~ Thu May 26 03:19:46 1994 +++ linux/drivers/block/blk.h Tue May 31 15:22:52 1994 @@ -82,6 +82,7 @@ extern unsigned long hd_init(unsigned long mem_start, unsigned long mem_end); extern unsigned long cdu31a_init(unsigned long mem_start, unsigned long mem_end); extern unsigned long mcd_init(unsigned long mem_start, unsigned long mem_end); +extern unsigned long dble_init(unsigned long mem_start, unsigned long mem_end); extern int is_read_only(int dev); extern void set_device_ro(int dev,int flag); @@ -194,6 +195,14 @@ #define DEVICE_NAME "Matsushita CD-ROM" #define DEVICE_REQUEST do_sbpcd_request #define DEVICE_NR(device) (MINOR(device)) +#define DEVICE_ON(device) +#define DEVICE_OFF(device) + +#elif (MAJOR_NR == DBLE_MAJOR) + +#define DEVICE_NAME "DouBle" +#define DEVICE_REQUEST do_db_request +#define DEVICE_NR(device) ((device) & 7) #define DEVICE_ON(device) #define DEVICE_OFF(device) --- linux/drivers/block/Makefile~ Thu May 26 03:19:46 1994 +++ linux/drivers/block/Makefile Tue May 31 15:22:52 1994 @@ -49,6 +49,11 @@ SRCS := $(SRCS) xd.c endif +ifdef CONFIG_DOUBLE +OBJS := $(OBJS) double.o dbtools.o lzw.o lzrw2.o lzrw3-a.o pred.o dbsuper.o lzv.o +SRCS := $(SRCS) double.c dbtools.c lzw.c lzrw2.c lzrw3-a.c pred.c dbsuper.c lzv.c +endif + all: block.a block.a: $(OBJS) --- linux/drivers/block/ll_rw_blk.c~ Thu May 26 03:19:46 1994 +++ linux/drivers/block/ll_rw_blk.c Tue Jun 7 14:12:01 1994 @@ -83,7 +83,14 @@ { static struct request *prev_found = NULL, *prev_limit = NULL; register struct request *req, *limit; +#ifdef CONFIG_DOUBLE + unsigned int major = MAJOR(dev); +/* DouBle request produce additional requests; they MUST not fill + * the request list. They also use more CPU time than regular requests. + */ + if(major == DBLE_MAJOR) n /= 4; +#endif if (n <= 0) panic("get_request(%d): impossible!\n", n); @@ -110,7 +117,7 @@ * NOTE: interrupts must be disabled on the way in, and will still * be disabled on the way out. */ -static inline struct request * get_request_wait(int n, int dev) +struct request * get_request_wait(int n, int dev) { register struct request *req; @@ -149,7 +156,7 @@ * It disables interrupts so that it can muck with the * request-lists in peace. */ -static void add_request(struct blk_dev_struct * dev, struct request * req) +void add_request(struct blk_dev_struct * dev, struct request * req) { struct request * tmp; @@ -229,45 +236,49 @@ * to add links to the top entry for scsi devices. */ if ((major == HD_MAJOR +#ifdef CONFIG_DBLE + || major == DBLE_MAJOR +#endif || major == SCSI_DISK_MAJOR || major == SCSI_CDROM_MAJOR) && (req = blk_dev[major].current_request)) { +#ifdef CONFIG_DBLE + if(major == HD_MAJOR || major = DBLE_MAJOR) +#else if (major == HD_MAJOR) +#endif req = req->next; - while (req) { + for (; req; req = req->next) { if (req->dev == bh->b_dev && !req->waiting && req->cmd == rw && - req->sector + req->nr_sectors == sector && - req->nr_sectors < 244) - { - req->bhtail->b_reqnext = bh; - req->bhtail = bh; - req->nr_sectors += count; - mark_buffer_clean(bh); - sti(); - return; +#ifdef CONFIG_DOUBLE +/* I don't want to pile up too many request on DouBle devices */ + (major != DBLE_MAJOR || req->nr_sectors < 32) && +#endif + req->nr_sectors < 244) { + if(req->sector + req->nr_sectors == sector) { + req->bhtail->b_reqnext = bh; + req->bhtail = bh; + req->nr_sectors += count; + mark_buffer_clean(bh); + sti(); + return; + } + + if(req->sector - count == sector) { + req->nr_sectors += count; + bh->b_reqnext = req->bh; + req->buffer = bh->b_data; + req->current_nr_sectors = count; + req->sector = sector; + mark_buffer_clean(bh); + req->bh = bh; + sti(); + return; + } } - - if (req->dev == bh->b_dev && - !req->waiting && - req->cmd == rw && - req->sector - count == sector && - req->nr_sectors < 244) - { - req->nr_sectors += count; - bh->b_reqnext = req->bh; - req->buffer = bh->b_data; - req->current_nr_sectors = count; - req->sector = sector; - mark_buffer_clean(bh); - req->bh = bh; - sti(); - return; - } - - req = req->next; } } @@ -395,8 +406,19 @@ queue, and then we let it rip. */ plugged = 0; + +/* I have a problem with this plugging stuff. We don't know what "max_req" + is going to be. If it turns out that nr > max_req, we're dead ! + */ cli(); +#ifdef CONFIG_DOUBLE + if(0) { +/* If you really want the plug thing back, you could use: + if(MAJOR(bh[0]->b_dev) != DBLE_MAJOR && !dev->current_request && nr>1) { + */ +#else if (!dev->current_request && nr > 1) { +#endif dev->current_request = &plug; plug.dev = -1; plug.next = NULL; @@ -406,6 +428,9 @@ for (i = 0; i < nr; i++) { if (bh[i]) { bh[i]->b_req = 1; +/* I may be a little insistent here, but what will happen if make_request + doesn't find a free request and we have plugged the device ? + */ make_request(major, rw, bh[i]); if (rw == READ || rw == READA) kstat.pgpgin++; @@ -497,6 +522,9 @@ #ifdef CONFIG_SBPCD mem_start = sbpcd_init(mem_start, mem_end); #endif CONFIG_SBPCD +#ifdef CONFIG_DOUBLE + mem_start = dble_init(mem_start, mem_end); +#endif if (ramdisk_size) mem_start += rd_init(mem_start, ramdisk_size*1024); return mem_start; --- linux/drivers/block/dbsuper.c~ Tue May 31 15:22:52 1994 +++ linux/drivers/block/dbsuper.c Tue May 31 15:22:52 1994 @@ -0,0 +1,97 @@ +/* + * linux/drivers/block/dbsuper.c + * + * Support for DOUBLE_FS; + * Copyright (c) 1994 Jean-Marc Verbavatz + */ + +#include +#include +#include +#include +#include +#include +#include +#include + +#ifdef CONFIG_DBLE_FS +static void dble_statfs(struct super_block *, struct statfs *); +extern void *dble_open(dev_t, struct inode *); +extern int dble_close(void *); +extern int get_bit(struct dble_device *, long); +extern void lock_db(void); +extern void unlock_db(void); + +extern struct dble_device dble_dev[]; + +void dble_put_super(struct super_block *s) +{ + if(dble_close(s->u.dble_sb.db)) + return; + lock_super(s); + s->s_dev = 0; + unlock_super(s); +} + +static struct super_operations dble_sops = { + NULL, + NULL, + NULL, + NULL, + dble_put_super, + NULL, + dble_statfs, + NULL +}; + +struct super_block *dble_read_super(struct super_block *s, + struct inode *inode, int silent) +{ + s->u.dble_sb.db = dble_open(s->s_dev, inode); + if(!s->u.dble_sb.db) { + s->s_dev = 0; + printk("DouBle device mount failed.\n"); + return NULL; + } + lock_super(s); + s->s_blocksize = 1024; + s->s_blocksize_bits = 10; + s->s_magic = DBLE_SUPER_MAGIC; + s->s_op = &dble_sops; + unlock_super(s); + return s; +} + +static void dble_statfs(struct super_block *s, struct statfs *buf) +{ + struct dble_device *db; + long free, total; + + db = s->u.dble_sb.db; + put_fs_long((long)DBLE_SUPER_MAGIC, &buf->f_type); + put_fs_long((long)db->isize, &buf->f_bsize); + lock_db(); + for(total = free = 0; total < db->iblocks; total++) + if(get_bit(db, total)) free++; + unlock_db(); + put_fs_long(total, &buf->f_blocks); /* Total blocks */ + put_fs_long(free, &buf->f_bfree); /* Total free blocks */ + put_fs_long(free, &buf->f_bavail); /* Total available blocks */ + put_fs_long(1, &buf->f_files); + put_fs_long(0, &buf->f_ffree); + put_fs_long(0, &buf->f_namelen); +} + +int dble_may_umount(dev_t dev) +{ + if(MAJOR(dev) != MAJOR_NR) /* I don't know what this is */ + return 0; + dev = MINOR(dev)&0x7f; + if(dev >= MAX_DBLE) + return 0; + if(dble_dev[dev].db_refcnt > 0) + return 0; + return 1; +} + +#endif --- linux/drivers/block/dbtools.c~ Tue May 31 15:22:52 1994 +++ linux/drivers/block/dbtools.c Tue Jun 7 11:00:49 1994 @@ -0,0 +1,576 @@ +/* /linux/drivers/block/double/dbtools.c + * + * Written by Jean-Marc Verbavatz + * 8 Jan 1994 + * + * Copyright 1994 by Jean-Marc Verbavatz. Redistribution of this + * file is permitted under the GNU Public Licence + */ + +#include +#include +#include +#include +#include +#include +#include "blk.h" +#include + +void add_request(struct blk_dev_struct *, struct request *); +struct request *get_request_wait(int, int); + +char *db_buffer; +long *db_mapbuf=NULL; +static struct db_header db_header; +struct buffer_head **db_bh; + +/* Load bitmap for block n into memory */ +int get_bitmap(struct dble_device *db, long n) +{ + if(db->bitmap_pos==n) return 1; /* already loaded */ + if(db->bitmap_mod) /* update */ + if(!db_rw_iblock(db, WRITE, db->bitmap_pos+db->addr_bitmap, db->bitmap)) + return 0; + else db->bitmap_mod = 0; + /* read new one */ + if(db_rw_iblock(db, READ, n+db->addr_bitmap, db->bitmap)) { + db->bitmap_pos = n; + return 1; + } + return 0; +} + + +/* Load BAT for cluster n into memory */ +int get_BAT(struct dble_device *db, long n) +{ + long i; + + + if(db->debug >= 10) printk("get_bat\n"); + i = n/(db->isize/db->BATsize); + if(db->BAT_pos!=i) { + if(db->BAT_mod) /* Flush */ + if(!db_rw_iblock(db, WRITE, db->BAT_pos+db->addr_BAT, db->BAT_block)) + return 0; + else db->BAT_mod = 0; +/* Load appropriate BAT block into memory */ + if(!db_rw_iblock(db, READ, i+db->addr_BAT, db->BAT_block)) + return 0; + db->BAT_pos = i; + } + return 1; +} + +/* The driver has its own db_getblk, db_bmap functions as + * the kernel functions getblk and bmap cannot be called reliably + * from within a driver. + */ + +/* get real block number for regular file block. This information is + * stored in blocks 1 to addr_bitmap and is updated by the + * set_fd ioctl call, when the device is mounted. + */ +long db_bmap(struct dble_device *db, long block) +{ + int n; + + if(block<(n=db->isize/sizeof(long))) return db->bmap0[block]; + else { + if(!db_rw_iblock(db, READ, block/n, (u_char *) db_mapbuf)) + return 0; + return db_mapbuf[block%n]; + } +} + +/* Add request to physical device queue */ +void ll_rw_dble(int rw, struct buffer_head *bh) +{ +struct request *req; +int dev = bh->b_dev; + + if(rw == WRITE && is_read_only(dev)) { + printk("DouBle: can't write to read-only device\n"); + bh->b_dirt = bh->b_uptodate = 0; + return; + } + lock_buffer(bh); + cli(); + req = get_request_wait(((rw == READ) ? (NR_REQUEST*3)>>2 : (NR_REQUEST<<1)/3), dev); + sti(); + req->cmd = rw; + req->errors = 0; + req->sector = bh->b_blocknr * (bh->b_size>>9); + req->nr_sectors = req->current_nr_sectors = bh->b_size>>9; + req->buffer = bh->b_data; + req->bh = req->bhtail = bh; + add_request(blk_dev+MAJOR(dev), req); +} + +/* make buffer n available */ +void move_queue(struct buffer_head *bh, int n) +{ + int i; + + for( i = n; i > 0; i--) + db_bh[i] = db_bh[i-1]; + *db_bh = bh; + if(bh->b_dirt == 1) wait_on_buffer(bh); +/* Make sure it's not still in use */ + if(bh->b_count != 0) { + printk("DouBle: too few bh buffers\n"); + wait_on_buffer(bh); + if(bh->b_count != 0) + panic("db_getblk: logical error count=%d\n", bh->b_count); + } + bh->b_count = 1; +} + + +/* get internal block buffer for physical block */ +struct buffer_head *db_getblk(dev_t dev, long block, int size) +{ + struct buffer_head *bh; + int i; + +/* Check to see if block is already in a buffer */ + for(i = 0; ib_dev == dev && bh->b_blocknr == block) { /* Yes */ + dble_stat.ihit++; + move_queue(bh, i); + return bh; + } + } +/* Not in cache; get free buffer */ + dble_stat.inohit++; + bh = db_bh[DB_NR_BH-1]; + if(bh->b_dirt==2) { /* needs to be written */ + bh->b_dirt = 1; + ll_rw_dble(WRITE, bh); + dble_stat.wphysical++; + } + move_queue(bh, DB_NR_BH - 1); + lock_buffer(bh); +/* Clean bh structure */ + bh->b_dev = dev; + bh->b_blocknr = block; + bh->b_uptodate = 0; + bh->b_req = 1; + bh->b_dirt = 0; + bh->b_size = size; + bh->b_reqnext = NULL; + unlock_buffer(bh); + return bh; +} + +/* Read/Write block */ +int db_rw_iblock(struct dble_device *db, int cmd, long n, u_char *s) +{ + int size, len, blksize, offset; + long block, rblock; + struct buffer_head *bh; + + if(db->debug >= 10) printk("db_rw+iblock: %ld\n", n); + if(n<0 || n>=db->iblocks) { + printk("db_rw_iblock: %ld/%ld non existent block\n", n, db->iblocks); + return 0; + } + if(!(blksize=db->db_inode->i_blksize)) + blksize=BLOCK_SIZE; + if(blksize<=db->isize) { + block=n*(db->isize/blksize); + offset=0; + } else { + block=n/(blksize/db->isize); + offset=(n%(blksize/db->isize))*db->isize; + } + len=db->isize; + while(len>0) { + if(db->db_flags & DB_BMAP) { + rblock = db_bmap(db, block); + if(!rblock) { + printk("db_rw_iblock: NULL block %ld %ld\n", n, block); + return 0; + } + } else rblock = block; + bh = db_getblk(db->db_device, rblock, blksize); + if(!bh->b_uptodate && ((cmd==READ) || offset || (lendebug >= 6) printk("DB_RW ll_rw READ\n"); + wait_on_buffer(bh); + if(!bh->b_uptodate) { + bh->b_count --; + printk("db_rw_iblock: failure\n"); + return 0; + } + } + size = blksize - offset; + if(size>len) size=len; + if(cmd==READ) { + memcpy(s, bh->b_data+offset, size); + } else + /* Write only if data changed */ + if(!bh->b_uptodate || memcmp(bh->b_data+offset, s, size)) { + memcpy(bh->b_data+offset, s, size); + bh->b_dirt=2; + } + bh->b_count --; + s+=size; + len-=size; + offset=0; + block++; + if(db->debug >= 5) printk("DB_RW DONE\n"); + } + return 1; +} + +/* find free block in bitmap */ +u_long get_newbit(db) +struct dble_device *db; +{ + int j,k,l; + u_long i,b; + + if(db->debug >= 10) printk("get_newbit\n"); + b = db->first_free; /* This is a reasonable way to start */ + if(!get_bitmap(db, b)) return 0; + i = (b*db->isize)<<3; + for(; ;) { + for(j = 0; j < db->isize; j++) if((k = db->bitmap[j]) != 0) { + for(l = 0x80; l; l >>= 1, i++) + if(k&l) { + k &= ~l; + db->bitmap[j] = k; + db->bitmap_mod = 1; + i += j<<3; + db->first_free = b; + return i; + } + } + i += j<<3; + if(i >= db->iblocks) { /* go back to beginning */ + b = -1; + i = 0; + } + if(++b == db->first_free) { /* Wrapped; not block free */ + printk("get_new_bit: out of space\n"); +/* The driver does not recover well from such errors + * I am seeking ways to recollect disk space in such emergency, + * but this does not seem to be trivial + */ + return 0; + } + if(!get_bitmap(db, b)) return 0; + } +} + +/* clear free bit (block is being used) */ +int clr_bit(struct dble_device *db, u_long n) +{ + u_long i; + + if(db->debug >= 10) printk("clr_bit\n"); + i = n/(db->isize<<3); + n = n%(db->isize<<3); + if(!get_bitmap(db, i)) return 0; + db->bitmap[n>>3] &= ~(0x80>>(n&7)); + db->bitmap_mod = 1; + return 1; +} + +/* set free bit (block has been released) */ +int set_bit(struct dble_device *db, u_long n) +{ + u_long i; + + if(db->debug >= 10) printk("set_bit\n"); + i = n/(db->isize<<3); + n = n%(db->isize<<3); + if(!get_bitmap(db, i)) return 0; + db->bitmap[n>>3] |= (0x80>>(n&7)); + db->bitmap_mod = 1; + return 1; +} + +/* return value of bit n */ +int get_bit(struct dble_device *db, u_long n) +{ + u_long i; + + i = n/(db->isize<<3); + n = n%(db->isize<<3); + if(!get_bitmap(db, i)) return -1; + return (db->bitmap[n>>3] & (0x80>>(n&7))); +} + +/* Read one cluster */ +int read_cluster(struct v_buffer *vbuf) +{ + u_char *t; + u_long *p; + struct BAT *b; + int i; + struct dble_device *db; + long n; + + db = vbuf->db; + n = vbuf->block; + if(db->debug >= 10) printk("read_cluster\n"); + if(n<0 || n>=db->oblocks) { + printk("read_cluster: %ld/%ld non existent cluster\n", n, db->oblocks); + return 0; + } + dble_stat.roblock++; + + if(!get_BAT(db, n)) return 0; + b = (struct BAT *)(db->BAT_block+db->BATsize*(n%(db->isize/db->BATsize))); + if(b->type == -1) { /* Unused (empty) */ + memset(vbuf->data, 0, db->osize); + return 1; + } + +/* Fetch compressed data in db_buffer */ + for(i = 0, t = db_buffer, p = &(b->iblock); *p && iratio; + i++, p++, t += db->isize) { + if(!db_rw_iblock(db, READ, *p, t)) return 0; + } + +/* decompress data */ + switch(b->type) { + case 0: memcpy(vbuf->data, db_buffer, db->osize); + break; + case 1: /* LZW */ + RLZW((code *)db_buffer, vbuf->data, db->osize); + break; + case 10: /* Algorithm used for predictor */ + rpred(db_buffer, vbuf->data, db->osize); + break; + case 101: /* FIN */ + break; + case 102: /* LZV */ + rLZV(db_buffer, vbuf->data, db->osize); + break; + case 212: /* LZRW2 12 bits */ + rlzrw2(db_buffer, vbuf->data, db->osize); + break; + case 312: /* LZRW3A */ + rlzrw3a(db_buffer, vbuf->data, db->osize); + break; + default: printk("Decompression error\n"); + return 0; + } + + return 1; +} + +/* write one cluster */ +int write_cluster(struct v_buffer *vbuf) +{ + int i,l; + u_long *p; + struct BAT *b; + struct dble_device *db; + long n; + u_char *s; + + db = vbuf->db; + n = vbuf->block; + s = vbuf->data; + if(db->debug >= 10) printk("write_cluster\n"); + if(n < 0 || n >= db->oblocks) { + printk("write_cluster: %ld/%ld non existent cluster\n", n, db->oblocks); + return 0; + } + dble_stat.woblock++; + + if(!get_BAT(db, n)) return 0; + b = (struct BAT *)(db->BAT_block+db->BATsize*(n%(db->isize/db->BATsize))); + +/* Compress data */ + l = db->code; + i = db->osize - db->isize; + switch(l) { + case 0: i = db->osize; + break; + case 1: /* LZW */ + i = WLZW(s, (code *)db_buffer, db->osize, i); + if(i<0) { + printk("WLZW error %d\n", i); + return 0; + } + if(i > 0) s = db_buffer; + break; + case 10: /* predictor's algorithm */ + wpred(s, db->osize, db_buffer, &i); + if(i>0) s = db_buffer; + break; + case 101: /* FIN */ + break; + case 102: /* LZV */ + wLZV(s, db_buffer, db->osize, &i); + if(i > 0) s = db_buffer; + break; + case 212: /* LZRW2 */ + wlzrw2(s, db->osize, db_buffer, &i); + if(i > 0) s = db_buffer; + break; + case 312: /* LZRW3A */ + wlzrw3a(s, db->osize, db_buffer, &i); + if(i > 0) s = db_buffer; + break; + default: printk("Compression error\n"); + return 0; + } + + if(i == 0) { /* No effective compression was achieved */ + l = 0; + i = db->osize; + } + if(b->type != l) { /* Cluster has compression method */ + b->type = l; + db->BAT_mod = 1; + } + l = i/db->isize; /* Number of blocks */ + if(i%db->isize) l++; + for(p=&(b->iblock), i=0; itype = -1; + db->BAT_mod = 1; + db->code = 312; + for(p=&(b->iblock), i = 0; i< db->ratio; i++, p++) { + set_bit(db, *p); + *p = 0; + } + return 0; + } + else db->BAT_mod = 1; + if(!db_rw_iblock(db, WRITE, *p, s)) return 0; + s+=db->isize; + } + for(;iratio;i++,p++) { + if(*p) { /* Fewer blocks used than before */ + if(!set_bit(db, *p)) return 0; /* release block */ + *p=0; + db->BAT_mod = 1; + } + else break; + } + + return 1; +} + +/* Launch write requests */ +void db_write_bbuffers(void) +{ + int i; + + for(i = DB_NR_BH; i-->0;) { + if(db_bh[i]->b_dirt==2) { /* need to write */ + db_bh[i]->b_dirt = 1; + ll_rw_dble(WRITE, db_bh[i]); + dble_stat.wphysical++; + } + } +} + +/* Flush all internal buffers */ +int db_flush(struct dble_device *db, int wait) +{ + int i, n, result = 0; + +if(db->debug) printk("db_flush: %d\n", wait); +/* Flush bitmap */ + if(db->bitmap_mod) + if(!db_rw_iblock(db, WRITE, db->bitmap_pos+db->addr_bitmap, db->bitmap)) + result = -1; + else db->bitmap_mod = 0; +if(db->debug >= 11) printk("db_flush: bitmap flushed\n"); +/* Flush BAT */ + if(db->BAT_mod) + if(!db_rw_iblock(db, WRITE, db->BAT_pos+db->addr_BAT, db->BAT_block)) + result = -1; + else db->BAT_mod = 0; +if(db->debug >= 11) printk("db_flush: BAT flushed\n"); + +/* Flush buffers */ + db_write_bbuffers(); + if(wait) { + for(i = DB_NR_BH; i-->0;) + if(db_bh[i]->b_dirt) + wait_on_buffer(db_bh[i]); + for(i = DB_NR_BH, n = 0; i-->0;) + if(db_bh[i]->b_count) n++; + if(n>0) printk("db_flush: %d buffers still in use\n", n); + } +if(db->debug >= 11) printk("db_flush: buffers flushed\n"); + return result; +} + +/* Read header from disk */ +int db_rheader(struct dble_device *db) +{ + long block; + int blksize; + struct buffer_head *bh; + + if(db->db_flags & DB_BMAP) /* Regular file, get real address */ + block = bmap(db->db_inode, 0); + else block = 0; + if(!(blksize = db->db_inode->i_blksize)) + blksize = BLOCK_SIZE; + bh = getblk(db->db_device, block, blksize); + if(!bh->b_uptodate) ll_rw_block(READ, 1, &bh); + + wait_on_buffer(bh); + memcpy(&db_header, bh->b_data, sizeof(struct db_header)); + brelse(bh); + + if(db_header.magic != DB_MAGIC) { + printk("DouBle: wrong magic number\n"); + return 0; + } + db->isize = db_header.isize; + db->osize = db_header.osize; + if(db->osize > DB_MAXSZ) { + printk("DouBle: cluster size (%d) too big\n", db->osize); + return 0; + } + db->iblocks = db_header.iblocks; + db->oblocks = db_header.oblocks; + db->addr_bitmap = db_header.addr_bitmap; + db->addr_BAT = db_header.addr_BAT; + db->addr_blocks = db_header.addr_blocks; + db->BATsize = db_header.BATsize; + db->ratio = db_header.ratio; + db->code = db_header.code; + db->bitmap_pos = -1; + db->bitmap_mod = 0; + db->BAT_pos = -1; + db->BAT_mod = 0; + db->first_free = 0; + db->debug = 0; + + db->bitmap = kmalloc(db->isize, GFP_KERNEL); + db->BAT_block = kmalloc(db->isize, GFP_KERNEL); + + if(db->db_flags & DB_BMAP) { + db->bmap0 = (long *) kmalloc(db->isize, GFP_KERNEL); + if(db->bmap0 == NULL) { + printk("DouBle: kmalloc returned NULL\n"); + return 0; + } + for(blksize = 0; blksize < db->isize/sizeof(long); blksize++) + db->bmap0[blksize] = bmap(db->db_inode, (long)blksize); + } else db->bmap0 = NULL; + if(db->bitmap == NULL || db->BAT_block == NULL) { + if(db->bitmap) kfree_s(db->bitmap, db->isize); + if(db->BAT_block) kfree_s(db->BAT_block, db->isize); + if(db->bmap0) kfree_s(db->bmap0, db->isize); + printk("DouBle: kmalloc returned NULL\n"); + return 0; + } + return 1; +} --- linux/drivers/block/double.c~ Tue May 31 15:22:52 1994 +++ linux/drivers/block/double.c Mon Jun 6 11:31:42 1994 @@ -0,0 +1,582 @@ +/* + * linux/drivers/block/double.c + * + * Adapted from loop.c (Copyright 1993 by Theodore Ts'o) + * by Jean-Marc Verbavatz 12 Jan 1994 + * + * Copyright 1994 by Jean-Marc Verbavatz. Redistribution of this file + * is permitted under the GNU Public License. + * + */ + +#include +#include +#include +#include +#include +#include +#include +#include "blk.h" + +struct v_buffer **db_vb; + +struct dble_device dble_dev[MAX_DBLE]; +static int dble_sizes[MAX_DBLE]; + +/* Synchronize requests (ioctl vs kernel ...) */ +static int in_request = 0; +static struct wait_queue *wait_on_request; + +extern char *db_buffer; +extern long *db_mapbuf; + +extern void db_write_bbuffers(void); +extern int iLZW(void *); +extern int ilzrw2(void *); +extern int ilzrw3a(void *); +extern int ipred(void *); +extern long iLZV(void *); + +/* Process synchronization; at any given time, only one process can + * use the driver + */ +void lock_db(void) +{ + cli(); + while(in_request) + sleep_on(&wait_on_request); + in_request = 1; + sti(); +} + +void unlock_db(void) +{ + in_request = 0; + wake_up(&wait_on_request); +} + +/* Get buffer for request */ +struct v_buffer *get_v_buffer(struct dble_device *db, long block) +{ + int i; + struct v_buffer *v_buffer; + + for(i = 0; i < DB_NR_VB; i++) + if(db_vb[i]->db_dev == db->db_number && db_vb[i]->block == block) break; + if(i < DB_NR_VB) { + dble_stat.ohit++; + v_buffer = db_vb[i]; + } else { + dble_stat.onohit++; + v_buffer = db_vb[--i]; + v_buffer->block = block; + v_buffer->db = db; + v_buffer->db_dev = db->db_number; + v_buffer->clean = 0; + } + for(; i > 0; i--) + db_vb[i] = db_vb[i-1]; + db_vb[0] = v_buffer; + return v_buffer; +} + +/* DouBle driver request loop */ +static void do_db_request(void) +{ + int offset, len, size; + long block, total_len; + char *dest_addr; + struct dble_device *db; + struct buffer_head *bh; + struct v_buffer *v_buffer; + struct request *req; + +/* Synchronize with ioctl/other calls */ + lock_db(); +repeat: +/* INIT_REQUEST */ + sti(); + if(!(req = CURRENT)) { /* No requests pending */ + for(len = 0; len < MAX_DBLE; len++) { + db = &dble_dev[len]; + if(db->db_inode) db_flush(db, 0); + } + unlock_db(); + return; + } + if(MAJOR(req->dev) != MAJOR_NR) + panic(DEVICE_NAME ": request list destroyed."); + if((bh = req->bh) && !bh->b_lock) + panic(DEVICE_NAME ": block not locked."); +/* Additional checking */ + if ((MINOR(req->dev)&0x7f) >= MAX_DBLE) + goto error_out; + db = &dble_dev[MINOR(req->dev)&0x7f]; + if (!db->db_inode) + goto error_out; + if ((req->cmd != WRITE) && (req->cmd != READ)) { + printk("DouBle: unknown command (%d)", req->cmd); + goto error_out; + } + if(db->debug >= 3) printk("INIT REQ\n"); + +/* Compute device block/offset */ + if (db->osize < 512) { /* Somewhat unlikely, but ... */ + block = req->sector * (512/db->osize); + offset = 0; + } else { + block = req->sector / (db->osize>>9); + offset = (req->sector % (db->osize>>9))<<9; + } + dest_addr = req->buffer; + total_len = req->nr_sectors<<9; + if(bh) /* Are we working block by block ? */ + len = bh->b_size; + else len = total_len; /* Only one buffer (swap) ... */ + +/* Process one request */ + while (total_len > 0) { + if(db->debug >= 12) printk("Cluster: %ld\n", block); + v_buffer = get_v_buffer(db, block); + if (!v_buffer->clean && + (req->cmd == READ || offset || total_len < db->osize)) { + if(!read_cluster(v_buffer)) { + printk("DouBle: read error "); + goto error_out; + } + v_buffer->clean = 1; + } + /* Process one cluster */ + do { + size = db->osize - offset; + if (size > len) size = len; + if(req->cmd == READ) { + dble_stat.rvirtual++; + memcpy(dest_addr, v_buffer->data+offset, size); + } else { + dble_stat.wvirtual++; + memcpy(v_buffer->data+offset, dest_addr, size); + v_buffer->clean = 2; /* Dirty */ + } + total_len -= size; + offset += size; + /* check for end of cluster */ + if(offset >= db->osize || total_len <=0) break; + /* done with one buffer - next buffer if any */ + if(!bh) break; + req->bh = bh->b_reqnext; + bh->b_reqnext = NULL; + bh->b_uptodate = 1; + unlock_buffer(bh); + bh = req->bh; + if(bh == NULL) break; + dest_addr = req->buffer = bh->b_data; + len = bh->b_size; + req->current_nr_sectors = len >> 9; + } while(total_len > 0); + + if(v_buffer->clean == 2) { + if(!write_cluster(v_buffer)) { + printk("DouBle: write error\n"); + goto error_out; + } + else v_buffer->clean = 1; + } +/* Get ready for next cluster */ + len -= size; + dest_addr += size; + offset = 0; + block++; + } + db_write_bbuffers(); + if(db->debug >= 3) printk("REQ DONE\n"); + cli(); /* end_request is going to shuffle the request list */ + end_request(1); +/* We're using a lot of resources - give a chance to other processes */ + sti(); + schedule(); + goto repeat; +error_out: + cli(); + end_request(0); + goto repeat; +} + +/* Update block map in regular file used as device + * The first isize/sizeof(long) block are loaded in memory by rheader + * block map starts on iblock # 1. + */ +int write_bmap(struct dble_device *db) +{ + register int i, j, n; + long block, save; + + n = db->isize/sizeof(long); + save = dble_stat.wphysical; + for(i = 1; i < db->addr_bitmap; i++) { + memset(db->BAT_block, 0, db->isize); + for(j = 0; j < n;) { + if(!(block = bmap(db->db_inode, i*n+j))) + break; + else ((long *)db->BAT_block)[j++] = block; + } + db_rw_iblock(db, WRITE, i, db->BAT_block); + if((i&15) == 0) printk("."); + } + printk("\n"); + dble_stat.wphysical = save; + return 0; +} + +/* Mount device on DouBle device */ +static int dble_set_fd(struct dble_device *db, struct inode * inode) +{ + if (db->db_inode) return -EBUSY; + if (!inode) { + printk("dble_set_fd: NULL inode?!?\n"); + return -EINVAL; + } + db->db_flags = 0; + if (S_ISREG(inode->i_mode)) { + db->db_device = inode->i_dev; + db->db_flags |= DB_BMAP; + if(!db_mapbuf) + if(!(db_mapbuf = (long *)kmalloc(BLOCK_SIZE, GFP_KERNEL))) + return -EINVAL; + } else if (S_ISBLK(inode->i_mode)) + db->db_device = inode->i_rdev; + else return -EINVAL; + if(inode->i_blksize > BLOCK_SIZE) return -EINVAL; + db->db_inode = inode; + unlock_db(); + fsync_dev(db->db_device); + lock_db(); + if(!db_rheader(db)) { + db->db_inode = 0; + printk("DouBle: error reading header\n"); + return -EINVAL; + } + if(db->db_flags & DB_BMAP) + write_bmap(db); + unlock_db(); + invalidate_buffers(db->db_device); + dble_sizes[db->db_number] = db->oblocks*db->osize/1024; + printk("DouBle Alpha Version 0.2b\n"); + printk("double%d: %ld clusters of %d bytes (%dK).\n", db->db_number, + db->oblocks, db->osize, dble_sizes[db->db_number]); + return 0; +} + +/* release device from DouBle device */ +static int dble_clr_fd(struct dble_device *db) +{ + int i; + struct inode *ino; + dev_t dev; + + if (db->db_refcnt > 0) return -EBUSY; + ino = db->db_inode; +/* flush and invalidate kernel buffers */ + dev = MKDEV(MAJOR_NR, db->db_number); + unlock_db(); + fsync_dev(dev); + fsync_dev(dev|0x80); + invalidate_buffers(dev); + invalidate_buffers(dev|0x80); +/* flush and invalidate internal buffers */ + lock_db(); + db_flush(db, 1); + iput(db->db_inode); + db->db_inode = 0; + dble_sizes[db->db_number] = 0; + for(i=0; ib_dev == db->db_device) + db_bh[i]->b_dev = -1; + for(i=0; idb_dev == db->db_number) { + db_vb[i]->db_dev = -1; + db_vb[i]->clean = 0; + } + db->db_device = 0; + kfree_s(db->bitmap, db->isize); + kfree_s(db->BAT_block, db->isize); + if(db->db_flags & DB_BMAP) kfree_s(db->bmap0, db->isize); + unlock_db(); + return 0; +} + +/* Function called by sys_mount via get_super, when using mount + * with DBLE_FS support instead of the ioctl call + */ +void *dble_open(dev_t dev, struct inode * inode) +{ + struct dble_device *db; + + if (MAJOR(dev) != MAJOR_NR) { + printk("db_ioctl: pseudo-major != %d\n", MAJOR_NR); + return NULL; + } + dev = MINOR(dev)&0x7f; + if (dev >= MAX_DBLE) return NULL; + db = &dble_dev[dev]; + if(dble_set_fd(db, inode)) + return NULL; + db->db_mounted = 1; + return (void *) db; +} + +/* Called by sys_umount via put_super, when using CONFIG_DBLE_FS */ +int dble_close(struct dble_device *db) +{ + + if(!db->db_inode) return -ENXIO; + if(!db->db_mounted) return -EBUSY; + return dble_clr_fd(db); +} + + +/* Change parameters (currently only default compression method) */ +static int dble_set_status(struct dble_device *db, struct dble_info *arg) +{ + struct dble_info info; + + if (!db->db_inode) return -ENXIO; + if (!arg) return -EINVAL; + memcpy_fromfs(&info, arg, sizeof(info)); + db->code = info.code; + return 0; +} + +static int dble_get_status(struct dble_device *db, struct dble_info *arg) +{ + struct dble_info info; + + if (!db->db_inode) return -ENXIO; + if (!arg) return -EINVAL; + memset(&info, 0, sizeof(info)); + info.oblocks = db->oblocks; + info.iblocks = db->iblocks; + info.osize = db->osize; + info.isize = db->isize; + info.code = db->code; + info.db_device = db->db_inode->i_dev; + info.db_inode = db->db_inode->i_ino; + info.db_rdevice = db->db_device; + info.db_flags = db->db_flags; + memcpy_tofs((struct dble_info *) arg, &info, sizeof(info)); + return 0; +} + +static int db_ioctl(struct inode * inode, struct file * file, + unsigned int cmd, unsigned long arg) +{ + struct dble_device *db; + int dev, err = 0; + + if (!inode) return -EINVAL; + if (!S_ISBLK(inode->i_mode)) return -ENXIO; + if (MAJOR(inode->i_rdev) != MAJOR_NR) { + printk("db_ioctl: pseudo-major != %d\n", MAJOR_NR); + return -ENODEV; + } + dev = MINOR(inode->i_rdev)&0x7f; + if (dev >= MAX_DBLE) return -ENODEV; + db = &dble_dev[dev]; + lock_db(); + switch (cmd) { + case DBLE_SET_FD: + if (arg >= NR_OPEN || !current->files->fd[arg]) return -EBADF; + err = dble_set_fd(db, current->files->fd[arg]->f_inode); + if(! err && db->db_inode) { + db->db_inode->i_count++; + db->db_mounted = 0; + } + break; + case DBLE_CLR_FD: + db->db_refcnt--; /* Was opened for ioctl */ + if (!db->db_inode) + err = -ENXIO; + /* Was it mounted or dbmounted ? */ + else if(db->db_mounted) + err = -EBUSY; /* Mounted */ + else /* dbmounted; we can go ahead */ + err = dble_clr_fd(db); + db->db_refcnt++; + break; + case DBLE_SET_STATUS: + err = dble_set_status(db, (struct dble_info *) arg); + break; + case DBLE_GET_STATUS: + err = dble_get_status(db, (struct dble_info *) arg); + break; + case DBLE_FLUSH: + err = db_flush(db, 1); + break; + case DBLE_STAT: + memcpy_tofs((struct dble_stat *) arg, &dble_stat, sizeof(dble_stat)); + break; + case BLKGETSIZE: /* Return device size */ + if (!db->db_inode) { + err = -ENXIO; + break; + } + if (!arg) { + err = -EINVAL; + break; + } + err = verify_area(VERIFY_WRITE, (long *) arg, sizeof(long)); + if (err) break; + put_fs_long(dble_sizes[db->db_number] << 1, (long *) arg); + break; + case DBLE_DEBUG: /* Set debug parameter */ + db->debug = arg; + break; + default: + err = -EINVAL; + } + unlock_db(); + return err; +} + +static int db_open(struct inode *inode, struct file *file) +{ + struct dble_device *db; + int dev; + + if (!inode) return -EINVAL; + if (MAJOR(inode->i_rdev) != MAJOR_NR) { + printk("db_open: pseudo-major != %d\n", MAJOR_NR); + return -ENODEV; + } + dev = MINOR(inode->i_rdev)&0x7f; + if (dev >= MAX_DBLE) return -ENODEV; + db = &dble_dev[dev]; + if(db->db_refcnt++ > 0) + printk("Warning: double%d is already open\n", db->db_number); + if(db->debug >= 11) printk("db_open\n"); + return 0; +} + +static void db_release(struct inode *inode, struct file *file) +{ + struct dble_device *db; + int dev; + + if (!inode) return; + if (MAJOR(inode->i_rdev) != MAJOR_NR) { + printk("db_release: pseudo-major != %d\n", MAJOR_NR); + return; + } + dev = MINOR(inode->i_rdev)&0x7f; + if (dev >= MAX_DBLE) return; + db = &dble_dev[dev]; +/* Synchronize with ioctl/request calls */ + lock_db(); + if(db->db_inode) db_flush(db, 1); + unlock_db(); + if (db->db_refcnt-- <= 0) { + printk("db_release: refcount < 0\n"); + db->db_refcnt = 0; + } + if(db->debug >= 11) printk("db_release\n"); + return; +} + +int db_fsync(struct inode *inode, struct file *file) +{ + struct dble_device *db; + int dev; + + if (!inode) return -EINVAL; + if (MAJOR(inode->i_rdev) != MAJOR_NR) { + printk("db_fsync: pseudo-major != %d\n", MAJOR_NR); + return -ENODEV; + } + dev = MINOR(inode->i_rdev)&0x7f; + if (dev >= MAX_DBLE) return -ENODEV; + db = &dble_dev[dev]; + if(db->debug) printk("db_fsync: %d\n", db->db_number); +/* Synchronize with ioctl/request calls */ + lock_db(); + if(db->db_inode) db_flush(db, 1); + unlock_db(); + return 0; +} + +static struct file_operations db_fops = { + NULL, /* lseek - default */ + block_read, /* read - general block-dev read */ + block_write, /* write - general block-dev write */ + NULL, /* readdir - bad */ + NULL, /* select */ + db_ioctl, /* ioctl */ + NULL, /* mmap */ + db_open, /* open */ + db_release, /* release */ + db_fsync /* fsync: I've never seen it called */ +}; + +/* + * Returns mem_start increased by the amount of memory which needs to be + * reserved. + */ +unsigned long dble_init(unsigned long mem_start, unsigned long mem_end) +{ + int i, l; + long mem0; + struct buffer_head *bh; + + mem0 = mem_start; + + if (register_blkdev(MAJOR_NR, "db", &db_fops)) { + printk("Unable to get major %d for DouBle device\n",MAJOR_NR); + return mem_start; + } + blk_dev[MAJOR_NR].request_fn = DEVICE_REQUEST; + for (i=0; i < MAX_DBLE; i++) { + memset(&dble_dev[i], 0, sizeof(struct dble_device)); + dble_dev[i].db_number = i; + } + dble_stat.ihit = dble_stat.inohit = + dble_stat.ihit = dble_stat.inohit = + dble_stat.roblock = dble_stat.woblock = + dble_stat.rvirtual = dble_stat.rphysical = + dble_stat.wvirtual = dble_stat.wphysical = 0; + memset(&dble_sizes, 0, sizeof(dble_sizes)); + blk_size[MAJOR_NR] = dble_sizes; + db_bh = (struct buffer_head **) mem_start; + mem_start += DB_NR_BH*sizeof(struct buffer_head *); + for(i=0; ib_data = (char *) mem_start; + bh->b_uptodate = bh->b_dirt = bh->b_count = bh->b_lock = 0; + bh->b_wait = NULL; + bh->b_dev = -1; + mem_start += BLOCK_SIZE; + } + db_vb = (struct v_buffer **) mem_start; + mem_start += DB_NR_VB*sizeof(struct v_buffer *); + for(i=0; idb_dev = -1; + db_vb[i]->db = NULL; + db_vb[i]->clean = 0; + mem_start += sizeof(struct v_buffer); + } + + db_buffer = (char *) mem_start; + mem_start += DB_MAXSZ; + l = iLZW((void *)mem_start); + i = iLZV((void *)mem_start); + if(i > l) l = i; + i = ilzrw2((void *)mem_start); + if(i > l) l = i; + i = ilzrw3a((void *)mem_start); + if(i > l) l = i; + i = ipred((void *)mem_start); + if(i > l) l = i; + mem_start += l; + printk("DouBle: %d devices, %d buffers %dK.\n", MAX_DBLE, DB_NR_BH+DB_NR_VB, (int)((mem_start-mem0)/1024)); + return mem_start; +} --- linux/drivers/block/lzrw2.c~ Tue May 31 15:22:52 1994 +++ linux/drivers/block/lzrw2.c Tue May 31 15:22:52 1994 @@ -0,0 +1,577 @@ +/******************************************************************************/ +/* */ +/* LZRW2.C */ +/* */ +/******************************************************************************/ +/* */ +/* Author : Ross Williams. */ +/* Date : 29-Jun-1991. */ +/* Release : 1. */ +/* */ +/******************************************************************************/ +/* */ +/* This file contains an implementation of the LZRW2 data compression */ +/* algorithm in C. */ +/* */ +/* The algorithm is a general purpose compression algorithm that runs fast */ +/* and gives reasonable compression. The algorithm is a member of the Lempel */ +/* Ziv family of algorithms and bases its compression on the presence in the */ +/* data of repeated substrings. */ +/* */ +/* Unlike the LZRW1 and LZRW1-A algorithms, the LZRW2 algorithm is */ +/* deterministic and is guaranteed to yield the same compressed */ +/* representation for a given file each time it is run. */ +/* */ +/* The LZRW2 algorithm was originally designed and implemented */ +/* by Ross Williams on 25-Nov-1990. */ +/* */ +/* Here are the results of applying this code compiled under THINK C 4.0 and */ +/* running on a Mac-SE (8MHz 68000) to the standard calgary corpus. */ +/* */ +/* +----------------------------------------------------------------+ */ +/* | DATA COMPRESSION TEST | */ +/* | ===================== | */ +/* | Time of run : Sat 29-Jun-1991 01:24PM | */ +/* | Timing accuracy : One part in 100 | */ +/* | Context length : 262144 bytes (= 256.0000K) | */ +/* | Test suite : Calgary Corpus Suite | */ +/* | Files in suite : 14 | */ +/* | Algorithm : LZRW2 | */ +/* | Note: All averages are calculated from the un-rounded values. | */ +/* +----------------------------------------------------------------+ */ +/* | File Name Length CxB ComLen %Remn Bits Com K/s Dec K/s | */ +/* | ---------- ------ --- ------ ----- ---- ------- ------- | */ +/* | rpus:Bib.D 111261 1 58726 52.8 4.22 16.98 52.36 | */ +/* | us:Book1.D 768771 3 491413 63.9 5.11 14.82 47.04 | */ +/* | us:Book2.D 610856 3 331932 54.3 4.35 17.10 51.28 | */ +/* | rpus:Geo.D 102400 1 84118 82.1 6.57 10.81 41.67 | */ +/* | pus:News.D 377109 2 215652 57.2 4.57 15.20 50.68 | */ +/* | pus:Obj1.D 21504 1 13032 60.6 4.85 13.13 50.15 | */ +/* | pus:Obj2.D 246814 1 119078 48.2 3.86 17.81 55.01 | */ +/* | s:Paper1.D 53161 1 28269 53.2 4.25 17.16 51.92 | */ +/* | s:Paper2.D 82199 1 46789 56.9 4.55 16.58 49.96 | */ +/* | rpus:Pic.D 513216 2 123311 24.0 1.92 33.17 71.63 | */ +/* | us:Progc.D 39611 1 19959 50.4 4.03 17.65 53.36 | */ +/* | us:Progl.D 71646 1 28571 39.9 3.19 22.63 59.13 | */ +/* | us:Progp.D 49379 1 19544 39.6 3.17 22.52 59.45 | */ +/* | us:Trans.D 93695 1 35364 37.7 3.02 22.87 60.89 | */ +/* +----------------------------------------------------------------+ */ +/* | Average 224401 1 115411 51.5 4.12 18.46 53.89 | */ +/* +----------------------------------------------------------------+ */ +/* */ +/******************************************************************************/ + +#include "lzrw.h" +/******************************************************************************/ + +/* The following structure is returned by the "compress" function below when */ +/* the user asks the function to return identifying information. */ +/* The most important field in the record is the working memory field which */ +/* tells the calling program how much working memory should be passed to */ +/* "compress" when it is called to perform a compression or decompression. */ +/* For the LZRW2 algorithm, the decompressor requires less memory than the */ +/* decompressor (so I have defined two constants) but the interface standard */ +/* I am using only allows a single memory size for both compression and */ +/* decompression so I put in the larger: CMP_MEM_REQ. */ +/* Note: CMP_MEM_REQ~=24K, DEC_MEM_REQ~=16K. */ +/* For more information on this structure see "lzrw.h". */ + +#define U(X) ((ULONG) X) +#define SIZE_P_BYTE (U(sizeof(UBYTE *))) +#define SIZE_WORD (U(sizeof(UWORD ))) +#define ALIGNMENT_FUDGE (U(100)) +#define CMP_MEM_REQ ( U(4096)*(SIZE_P_BYTE+SIZE_WORD) + ALIGNMENT_FUDGE ) +#define DEC_MEM_REQ ( U(4096)*(SIZE_P_BYTE ) + ALIGNMENT_FUDGE ) + +/*static struct compress_identity identity = +{ + U(0x3D8F733A), * Algorithm identification number. * + CMP_MEM_REQ, * Working memory (bytes) required. * + "LZRW2", * Name of algorithm. * + "1.0", * Version number of algorithm. * + "25-Nov-1990", * Date of algorithm. * + "Ross N. Williams", * Author of algorithm. * + "Renaissance Software", * Affiliation of author. * +};*/ + +/******************************************************************************/ +/* */ +/* BRIEF DESCRIPTION OF THE LZRW2 ALGORITHM */ +/* ======================================== */ +/* The LZRW2 algorithm is identical to the LZRW1-A algorithm except that it */ +/* employs a PHRASE TABLE. The phrase table contains pointers to the first */ +/* byte of the most recent 4096 phrases processed. A phrase is defined to be */ +/* a sequence of one or more bytes that are coded as a single literal or copy */ +/* item. Instead of coding a copy item as a length and an offset as LZRW1 */ +/* does, LZRW2 codes a copy item as a length and a phrase table index. The */ +/* result is that LZRW2 can point far further back than LZRW1 but without */ +/* increasing the number of bits allocated to the 'offset' in the coding. The */ +/* phrase table is incapable of pointing within phrases, but LZRW1 was */ +/* incapabale of doing that anyway because it only ever updated its hash */ +/* table on phrase boundaries. */ +/* */ +/* Updating the phrase table involves just writing a pointer to the next */ +/* position (which circulates) in the phrase table after each literal or */ +/* copy item is coded. The decompressor needs to maintain a phrase table but */ +/* not a hash table. */ +/* */ +/* Use of the phrase table yields a 3% absolute to 5% absolute improvement */ +/* over LZRW1-A in compression, does not affect compression speed, but */ +/* reduces decompression speed by about 30%. Thus LZRW2 does not dominate */ +/* LZRW1-A, as LZRW1-A does LZRW1. */ +/* */ +/* An extra 3% absolute compression can be obtained by using a hash table of */ +/* depth two. However, increasing the depth above one incurs a 40% decrease */ +/* in compression speed which was not considered worthwhile. Another reason */ +/* for keeping the depth down to one was to allow easy comparison with the */ +/* LZRW1-A algorithm so as to demonstrate the exact effect of the phrase */ +/* table. */ +/* */ +/* +---+ +---+ */ +/* |___|4095 |___|4095 */ +/* |___| |___| */ +/* Next-->|___| +-------*_|<---+ /----+---\ */ +/* (circles |___| | |___| +---|Hash | */ +/* through +---*_|<------+ |___| |Function| */ +/* phrase | |___| |___| \--------/ */ +/* table) | |___|0 |___|0 ^ */ +/* | +---+ +---+ | */ +/* | Phrase Hash +-----+ */ +/* | Table Table | */ +/* | --- */ +/* v ^^^ */ +/* +-------------------------------------|----------------+ */ +/* |||||||||||||||||||||||||||||||||||||||||||||||||||||||| */ +/* +-------------------------------------|----------------+ */ +/* | |1......18| | */ +/* |<------- Lempel=History ------------>|<--Ziv-->| | */ +/* | (=bytes already processed) |<-Still to go-->| */ +/* |<-------------------- INPUT BLOCK ------------------->| */ +/* */ +/* LZRW2 Algorithm Execution Summary */ +/* --------------------------------- */ +/* 1. Hash the first three bytes of the Ziv to yield a hash table index h. */ +/* 2. Look up the hash table yielding phrase table index i. */ +/* 3. Look up phrase i yielding a pointer p to the Lempel. */ +/* 4. Overwrite the 'next' cyclic entry in the phrase table with a pointer */ +/* to the Ziv. Increment the 'next' index (mod 4096). */ +/* 5. Overwrite hash table entry h with the index of the overwritten */ +/* position of step 4. */ +/* 6. Match where p points with the Ziv. If there is a match of three or */ +/* more bytes, code those bytes (in the Ziv) as a copy item, otherwise */ +/* code the next byte in the Ziv as a literal item. */ +/* */ +/******************************************************************************/ +/* */ +/* DEFINITION OF COMPRESSED FILE FORMAT */ +/* ==================================== */ +/* The file consists of zero */ +/* or more GROUPS, each of which represents one or more bytes. */ +/* * Each group consists of two bytes of CONTROL information followed by */ +/* sixteen ITEMs except for the last group which can contain from one */ +/* to sixteen items. */ +/* * An item can be either a LITERAL item or a COPY item. */ +/* * Each item corresponds to a bit in the control bytes. */ +/* * The first control byte corresponds to the first 8 items in the group */ +/* with bit 0 corresponding to the first item in the group and bit 7 to */ +/* the eighth item in the group. */ +/* * The second control byte corresponds to the second 8 items in the group */ +/* with bit 0 corresponding to the ninth item in the group and bit 7 to */ +/* the sixteenth item in the group. */ +/* * A zero bit in a control word means that the corresponding item is a */ +/* literal item. A one bit corresponds to a copy item. */ +/* * A literal item consists of a single byte which represents itself. */ +/* * A copy item consists of two bytes that represent from 3 to 18 bytes. */ +/* * The first byte in a copy item will be denoted C1. */ +/* * The second byte in a copy item will be denoted C2. */ +/* * Bits will be selected using square brackets. */ +/* For example: C1[0..3] is the low nibble of the first control byte. */ +/* of copy item C1. */ +/* * The LENGTH of a copy item is defined to be C1[0..3]+3 which is a number */ +/* in the range [3,18]. */ +/* * The INDEX of a copy item is defined to be C1[4..7]*256+C2[0..8] which */ +/* is a number in the range [0,4095]. */ +/* * A copy item represents the sequence of bytes */ +/* text[POS-OFFSET..POS-OFFSET+LENGTH-1] where */ +/* text is the entire text of the uncompressed string. */ +/* POS is the index in the text of the character following the */ +/* string represented by all the items preceeding the item */ +/* being defined. */ +/* OFFSET is obtained from INDEX by looking up the phrase table. */ +/* */ +/******************************************************************************/ + +/* Stylistic note: The LZRW1 algorithm was written in an extremely terse */ +/* style because it had to fit on a single page in a paper. This style */ +/* carried over to the LZRW1-A algorithm. However, LZRW2 has not been */ +/* published and so I have reverted to my normal programming style. */ + +/* Stylistic note: This code could be considerably neated by the use of */ +/* dependent declarations such as {int a=3,b=a+1;}. However I can't locate a */ +/* clause in K&R that guarantees that declarations are evaluated in order. */ + +/* The following constant defines the maximum length of an uncompressed item. */ +/* This definition must not be changed; its value is hardwired into the code. */ +/* The longest number of bytes that can be spanned by a single item is 18 */ +/* for the longest copy item. */ +#define MAX_RAW_ITEM (18) + +/* The following constant defines the maximum length of a compressed group. */ +/* This definition must not be changed; its value is hardwired into the code. */ +/* A compressed group consists of two control bytes followed by up to 16 */ +/* compressed items each of which can have a maximum length of two bytes. */ +#define MAX_CMP_GROUP (2+16*2) + +/* The following constant defines the number of entries in the phrase table. */ +/* This definition must not be changed; its value is hardwired into the code. */ +#define PHRASE_TABLE_LENGTH (4096) + +/* The following constant defines the number of entries in the hash table. */ +/* This definition must not be changed; its value is hardwired into the code. */ +#define HASH_TABLE_LENGTH (4096) + +/* At initialization, the hash table entries are all set to point to element */ +/* zero of the phrase table. In order for the algorithm to start up, */ +/* phrase[0] needs to point to a well defined string of at least 18 bytes. At */ +/* startup, there is no already-transmitted source text to point to and so */ +/* we have to invent some dummy text to point to. It doesn't matter what is */ +/* in this string so long as it is at least MAX_RAW_ITEM bytes long and is */ +/* the same in the compressor and decompressor. I chose consecutive decimal */ +/* digits because they do not have white space problems (e.g. there is no */ +/* chance that the compiler will replace more than one space by a TAB) and */ +/* because they make the length of the string obvious by inspection. */ +#define START_STRING_18 "123456789012345678" + +/******************************************************************************/ +UBYTE *p_wrk_mem; + +EXPORT int ilzrw2(void *mem_start) +{ +p_wrk_mem = mem_start; +return CMP_MEM_REQ; +} + +EXPORT void wlzrw2 + (p_src_first,src_len,p_dst_first,p_dst_len) +/* Input : Specify input block using p_src_first and src_len. */ +/* Input : Point p_dst_first to the start of the output zone (OZ). */ +/* Input : Point p_dst_len to a ULONG to receive the output length. */ +/* Input : Input block and output zone must not overlap. */ +/* Output : Length of output block written to *p_dst_len. */ +/* Output : Output block in Mem[p_dst_first..p_dst_first+*p_dst_len-1]. May */ +/* Output : write in OZ=Mem[p_dst_first..p_dst_first+src_len+MAX_CMP_GROUP-1].*/ + +UBYTE *p_src_first; +ULONG src_len; +UBYTE *p_dst_first; +ULONG *p_dst_len; +{ + /* p_src and p_dst step through the source and destination blocks. */ + register UBYTE *p_src = p_src_first; + register UBYTE *p_dst = p_dst_first; + + /* The following variables are never modified and are used in the */ + /* calculations that determine when the main loop terminates. */ + UBYTE *p_src_post = p_src_first+src_len; + UBYTE *p_dst_post = p_dst_first+*p_dst_len; + UBYTE *p_src_max1 = p_src_first+src_len-MAX_RAW_ITEM; + UBYTE *p_src_max16 = p_src_first+src_len-MAX_RAW_ITEM*16; + + /* The variables 'p_control' and 'control' are used to buffer control bits. */ + /* Before each group is processed, the next two bytes of the output block */ + /* are set aside for the control word for the group about to be processed. */ + /* 'p_control' is set to point to the first byte of that word. Meanwhile, */ + /* 'control' buffers the control bits being generated during the processing */ + /* of the group. Instead of having a counter to keep track of how many items */ + /* have been processed (=the number of bits in the control word), at the */ + /* start of each group, the top word of 'control' is filled with 1 bits. */ + /* As 'control' is shifted for each item, the 1 bits in the top word are */ + /* absorbed or destroyed. When they all run out (i.e. when the top word is */ + /* all zero bits, we know that we are at the end of a group. */ + #define TOPWORD 0xFFFF0000 + UBYTE *p_control; + ULONG control=TOPWORD; + + UWORD *hash; /* Points to the first element of the hash table. */ + UBYTE **phrase; /* Points to the first element of the phrase table. */ + register UWORD next; /* Index of next phrase entry to be overwritten. */ + + /* Set up the hash table and the phrase table in the memory given to */ + /* the algorithm. These tables are the only occupants of the memory. */ + hash = (UWORD *) p_wrk_mem; + phrase = (UBYTE **) &hash[HASH_TABLE_LENGTH]; + + /* The variable 'next' cycles through the phrase table indicating the next */ + /* position in the table to write a new phrase pointer. */ + next=0; + + /* Reserve the first word of output as the control word for the first group. */ + /* Note: This is undone at the end if the input block is empty. */ + p_control=p_dst; p_dst+=2; + + /* Initialize the hash table and the phrase table. The hash table entries */ + /* all point to element zero of the phrase table which in turn points to */ + /* a constant string. The remainder of the phrase table does not need to */ + /* be initialized as the algorithm is arranged so that no element of the */ + /* phrase table is ever read before it has been written. */ + /* In theory, either the hash table or the phrase table has to be */ + /* initialized. I chose the hash table as this choice yields determinism. */ + {register UWORD i,*t=hash; + #define ZH *t++=0; *t++=0; *t++=0; *t++=0 + for (i=0;i<256;i++) {ZH;ZH;ZH;ZH;} /* 256=HASH_TABLE_LENGTH/16 */ + } + phrase[0]=(UBYTE *) START_STRING_18; + + /* The main loop processes either 1 or 16 items per iteration. As its */ + /* termination logic is complicated, I have opted for an infinite loop */ + /* structure containing 'break' and 'goto' statements. */ + while (TRUE) + {/* Begin main processing loop. */ + + register UBYTE *p; /* Scans through targ phrase during matching. */ + register UBYTE *p_ziv; /* Points to first byte of current Ziv. */ + register UWORD phrase_num; /* Current phrase number (index in phr tab). */ + register UWORD unroll; /* Loop counter for unrolled inner loop. */ + register UWORD *p_hte; /* Pointer to the current hash table entry. */ + + /* Test for overrun and jump to overrun code if necessary. */ + if (p_dst>p_dst_post) + goto overrun; + + /* The following cascade of if statements efficiently catches and deals */ + /* with varying degrees of closeness to the end of the input block. */ + /* When we get very close to the end, we stop updating the tables and */ + /* code the remaining bytes as literals. This makes the code simpler. */ + unroll=16; + if (p_src>p_src_max16) + { + unroll=1; + if (p_src>p_src_max1) + { + if (p_src==p_src_post) + break; + else + goto literal; + } + } + + /* This inner unrolled loop processes 'unroll' (whose value is either 1 */ + /* or 16) items. I have chosen to implement this loop with labels and */ + /* gotos to heighten the ease with which the loop may be implemented with */ + /* a single decrement and branch instruction in assembly language and */ + /* also because the labels act as highly readable place markers. */ + /* (Also because we jump into the loop for endgame literals (see above)). */ + + begin_unrolled_loop: + + /* To process the next phrase, we hash the next three bytes and use */ + /* the resultant hash table index to look up the hash table. A pointer */ + /* to the entry is stored in p_hte. We store a pointer instead of an */ + /* index so as to avoid array lookups. The hash table entry contains a */ + /* phrase number 'phrase_num' which we use to look up the phrase table */ + /* and get a pointer 'p' to a potential match in the history. */ + p_hte=&hash[((40543*((p_src[0]<<8)^(p_src[1]<<4)^p_src[2]))>>4) & 0xFFF]; + phrase_num=*p_hte; + p=phrase[phrase_num]; + + /* Update the hash table and phrase table. The next element of the */ + /* phrase table points to the first byte of the current Ziv and the */ + /* hash table entry we looked up gets overwritten with the phrase */ + /* table entry number. Wraparound of 'next' is done elsewhere. */ + *p_hte=next; + phrase[next++]=p_src; + + /* Having looked up the candidate position, we are in a position to */ + /* attempt a match. The match loop has been unrolled using the PS */ + /* macro so that failure within the first three bytes automatically */ + /* results in the literal branch being taken. The coding is simple. */ + /* p_ziv saves p_src so we can let p_src wander. */ + #define PS *p++!=*p_src++ + p_ziv=p_src; + if (PS || PS || PS) + {p_src=p_ziv; literal:*p_dst++=*p_src++; control&=0xFFFEFFFF;} + else + { + PS || PS || PS || PS || PS || PS || PS || PS || + PS || PS || PS || PS || PS || PS || PS || p_src++; + *p_dst++=((phrase_num&0xF00)>>4)|(--p_src-p_ziv-3); + *p_dst++=phrase_num&0xFF; + } + control>>=1; + + /* This loop is all set up for a decrement and jump instruction! */ + if (--unroll) goto begin_unrolled_loop; + + /* At this point it will nearly always be the end of a group in which */ + /* case, we have to do some control-word processing. However, near the */ + /* end of the input block, the inner unrolled loop is only executed once. */ + /* This necessitates the 'if' test. */ + if ((control&TOPWORD)==0) + { + /* Write the control word to the place we saved for it in the output. */ + *p_control++= control &0xFF; + *p_control = (control>>8) &0xFF; + + /* Reserve the next word in the output block for the control word */ + /* for the group about to be processed. */ + p_control=p_dst; p_dst+=2; + + /* Reset the control bits buffer. */ + control=TOPWORD; + + /* The following statement makes sure that the 'next' phrase table */ + /* index cycles when it comes to the end of the phrase table. This */ + /* can be included here within the control word processing because the */ + /* control word processing happens once every 16 items processed and */ + /* 4096 (the num of entries in the phrase table) is a multiple of 16. */ + next&=0xFFF; + } + + } /* End main processing loop. */ + + /* After the main processing loop has executed, all the input bytes have */ + /* been processed. However, the control word has still to be written to the */ + /* word reserved for it in the output at the start of the most recent group. */ + /* Before writing, the control word has to be shifted so that all the bits */ + /* are in the right place. The "empty" bit positions are filled with 1s */ + /* which partially fill the top word. */ + while(control&TOPWORD) control>>=1; + *p_control++= control &0xFF; + *p_control++=(control>>8) &0xFF; + + /* If the last group contained no items, delete the control word too. */ + if (p_control==p_dst) p_dst-=2; + + /* Write the length of the output block to the dst_len parameter and return. */ + *p_dst_len=p_dst-p_dst_first; + return; + + /* Jump here as soon as an overrun is detected. An overrun is defined to */ + /* have occurred if p_dst>*p_dst_len as set by caller. */ + /* The algorithm checks for overruns at least at the end of each group */ + /* which means that the maximum overrun is MAX_CMP_GROUP bytes. */ + /* Once an overrun occurs, the only thing to do is to return with error */ + overrun: + *p_dst_len=0; +} + +/******************************************************************************/ + +EXPORT int rlzrw2 + (p_src_first, p_dst, dst_len) +/* Input : Specify input block using p_src_first. Point p_dst to the */ +/* Input : start of the output zone and length dst_len. */ +/* Input : Input block and output zone must not overlap. User knows */ +/* Input : upperbound on output block length from earlier compression. */ +/* Input : In any case, maximum expansion possible is nine times. */ +/* Output : Output block in Mem[p_dst..p_dst+dst_len-1]. */ +/* Output : Writes only in Mem[p_dst..p_dst+dst_len-1]. */ +UBYTE *p_src_first; +UBYTE *p_dst; +ULONG dst_len; +{ + /* Byte pointers scan through the input and output blocks. */ + register UBYTE *p_src = p_src_first; + + /* The following two variables are never modified and are used to control */ + /* the main loop. */ + UBYTE *p_dst_post = p_dst+dst_len; + UBYTE *p_dst_max16 = p_dst_post-MAX_RAW_ITEM*16; + + /* The variable 'control' is used to buffer the control bits which appear in */ + /* groups of 16 bits (control words) at the start of each compressed group. */ + /* When each group is read, bit 16 of the register is set to one. Whenever */ + /* a new bit is needed, the register is shifted right. When the value of the */ + /* register becomes 1, we know that we have reached the end of a group. */ + /* Initializing the register to 1 thus instructs the code to follow that it */ + /* should read a new control word immediately. */ + register ULONG control=1; + + /* The phrase table is the same as in the compressor. The decompressor does */ + /* not need to maintain a hash table, only a phrase table. */ + /* The phrase table is the only occupant of the working memory. */ + UBYTE **phrase = (UBYTE **) p_wrk_mem; + + /* The next variable cycles through the phrase table always containing the */ + /* index of the next phrase pointer to be overwritten in the phrase table. */ + /* Optimization note: I tried using a pointer to cycle through the table but */ + /* this went more slowly than using an explicit index. */ + register UWORD next=0; + + /* Whereas the compressor needs to maintain a hash table and a phrase table */ + /* the decompressor needs to maintain only the phrase table. Only the first */ + /* entry of the phrase table needs initializing as, apart from this entry, */ + /* the compressor guarantees not to refer to a table entry until the entry */ + /* has been written. */ + phrase[0]=(UBYTE *) START_STRING_18; + + /* The outer loop processes either 1 or 16 items per iteration depending on */ + /* how close p_src is to the end of the input block. */ + while (p_dst!=p_dst_post) + {/* Start of outer loop */ + + register UWORD unroll; /* Counts unrolled loop executions. */ + + /* When 'control' has the value 1, it means that the 16 buffered control */ + /* bits that were read in at the start of the current group have all been */ + /* shifted out and that all that is left is the 1 bit that was injected */ + /* into bit 16 at the start of the current group. When we reach the end */ + /* of a group, we have to load a new control word and inject a new 1 bit. */ + if (control==1) + { + control=0x10000|*p_src++; + control|=(*p_src++)<<8; + + /* Because 4096 (the number of entries in the phrase table) is a */ + /* multiple of 16 (the loop unrolling), and 'unroll' has the value 1 */ + /* or 16 and never increases its initial value, this wraparound check */ + /* need only be done once per main loop. In fact it can even reside */ + /* within this 'if'. */ + next&=0xFFF; + } + + unroll= p_dst <= p_dst_max16 ? 16 : 1; + + /* This inner loop processes one phrase (item) per iteration. */ + while (unroll--) + { /* Begin unrolled inner loop. */ + + /* Process a literal or copy item depending on the next control bit. */ + if (control&1) + { /* Copy item. */ + register UWORD lenmt; /* Length of copy item minus three. */ + register UBYTE *p; /* Points to history posn from which to copy. */ + + /* Read and dismantle the copy word. Work out from where to copy. */ + lenmt=*p_src++; + p=phrase[((lenmt&0xF0)<<4)|*p_src++]; + lenmt&=0xF; + + /* Update the phrase table. Don't do this before p=phrase[...]. */ + phrase[next++]=p_dst; + + /* Now perform the copy using a half unrolled loop. */ + *p_dst++=*p++; + *p_dst++=*p++; + *p_dst++=*p++; + while (lenmt--) + *p_dst++=*p++; + } + else + { /* Literal item. */ + phrase[next++]=p_dst; /* Update the phrase table. */ + *p_dst++=*p_src++; /* Copy over the literal byte. */ + } + + /* Shift the control buffer so the next control bit is in bit 0. */ + control>>=1; + + } /* End unrolled inner loop. */ + + } /* End of outer loop */ + return (p_src - p_src_first); +} + +/******************************************************************************/ +/* End of LZRW2.C */ +/******************************************************************************/ --- linux/drivers/block/lzrw3-a.c~ Tue May 31 15:22:52 1994 +++ linux/drivers/block/lzrw3-a.c Tue May 31 15:22:53 1994 @@ -0,0 +1,763 @@ +/******************************************************************************/ +/* */ +/* LZRW3-A.C */ +/* */ +/******************************************************************************/ +/* */ +/* Author : Ross Williams. */ +/* Date : 15-Jul-1991. */ +/* Release : 1. */ +/* */ +/******************************************************************************/ +/* */ +/* This file contains an implementation of the LZRW3-A data compression */ +/* algorithm in the C programming language. */ +/* */ +/* The LZRW3-A algorithm has the following features: */ +/* */ +/* 1 Requires only 16K of memory (for both compression and decompression). */ +/* 2 The compressor runs about two times faster than Unix compress's. */ +/* 3 The decompressor runs about three times faster than Unix compress's. */ +/* 4 Yields a few percent better compression than Unix compress for */ +/* most files. */ +/* 5 Allows you to dial up extra compression at a speed cost in the */ +/* compressor. The speed of the decompressor is not affected. */ +/* 6 Algorithm is deterministic. */ +/* 8 This implementation in C is in the public domain. */ +/* */ +/* (Timing tests for the speed comparison were performed on a Pyramid 9820.) */ +/* */ +/* LZRW3-A is LZRW3 with a deepened hash table. This simple change yields */ +/* about a 6% (absolute) improvement in compression. */ +/* */ +/* Here are the results of applying this code, compiled under THINK C 4.0 */ +/* and running on a Mac-SE (8MHz 68000), to the standard calgary corpus. */ +/* */ +/* +----------------------------------------------------------------+ */ +/* | DATA COMPRESSION TEST | */ +/* | ===================== | */ +/* | Time of run : Mon 15-Jul-1991 05:29PM | */ +/* | Timing accuracy : One part in 100 | */ +/* | Context length : 262144 bytes (= 256.0000K) | */ +/* | Test suite : Calgary Corpus Suite | */ +/* | Files in suite : 14 | */ +/* | Algorithm : LZRW3-A | */ +/* | Note: All averages are calculated from the un-rounded values. | */ +/* +----------------------------------------------------------------+ */ +/* | File Name Length CxB ComLen %Remn Bits Com K/s Dec K/s | */ +/* | ---------- ------ --- ------ ----- ---- ------- ------- | */ +/* | rpus:Bib.D 111261 1 49044 44.1 3.53 8.47 31.19 | */ +/* | us:Book1.D 768771 3 420464 54.7 4.38 7.27 30.07 | */ +/* | us:Book2.D 610856 3 277955 45.5 3.64 8.51 33.40 | */ +/* | rpus:Geo.D 102400 1 84218 82.2 6.58 4.23 15.04 | */ +/* | pus:News.D 377109 2 192880 51.1 4.09 7.08 25.89 | */ +/* | pus:Obj1.D 21504 1 12651 58.8 4.71 5.23 17.44 | */ +/* | pus:Obj2.D 246814 1 108044 43.8 3.50 8.01 28.11 | */ +/* | s:Paper1.D 53161 1 24526 46.1 3.69 8.11 30.24 | */ +/* | s:Paper2.D 82199 1 39483 48.0 3.84 8.11 32.04 | */ +/* | rpus:Pic.D 513216 2 111622 21.7 1.74 10.64 49.31 | */ +/* | us:Progc.D 39611 1 17923 45.2 3.62 8.06 29.01 | */ +/* | us:Progl.D 71646 1 24362 34.0 2.72 10.74 39.51 | */ +/* | us:Progp.D 49379 1 16805 34.0 2.72 10.64 37.58 | */ +/* | us:Trans.D 93695 1 30296 32.3 2.59 11.02 38.06 | */ +/* +----------------------------------------------------------------+ */ +/* | Average 224401 1 100733 45.8 3.67 8.29 31.21 | */ +/* +----------------------------------------------------------------+ */ +/* */ +/******************************************************************************/ + +#include "lzrw.h" +/******************************************************************************/ + +/* The following structure is returned by the "compress" function below when */ +/* the user asks the function to return identifying information. */ +/* The most important field in the record is the working memory field which */ +/* tells the calling program how much working memory should be passed to */ +/* "compress" when it is called to perform a compression or decompression. */ +/* LZRW3-A uses the same amount of memory during compression and */ +/* decompression. For more information on this structure see "lzrw.h". */ +/* The alignment fudge below really only needs to be 4 (but I play it safe!). */ +/* The id looks non-random, but it really was generated by coin tossing! */ + +#define U(X) ((ULONG) X) +#define SIZE_P_BYTE (U(sizeof(UBYTE *))) +#define ALIGNMENT_FUDGE (U(16)) +#define MEM_REQ ( U(4096)*(SIZE_P_BYTE) + ALIGNMENT_FUDGE ) + +/*static struct compress_identity identity = +{ + U(0x01B90B91), * Algorithm identification number. * + MEM_REQ, * Working memory (bytes) required. * + "LZRW3-A", * Name of algorithm. * + "1.0", * Version number of algorithm. * + "15-Jul-1990", * Date of algorithm. * + "Ross N. Williams", * Author of algorithm. * + "Renaissance Software", * Affiliation of author. * +};*/ + +/******************************************************************************/ +/* */ +/* BRIEF DESCRIPTION OF THE LZRW3-A ALGORITHM */ +/* ========================================== */ +/* Note: Before attempting to understand this algorithm, you should first */ +/* understand the LZRW3 algorithm from which this algorithm is derived. */ +/* */ +/* The LZRW3-A algorithm is identical to the LZRW3 algorithm except that the */ +/* hash table has been "deepened". The LZRW3 algorithm has a hash table of */ +/* 4096 pointers which point to strings in the buffer. LZRW3-A generalizes */ +/* this to 4096/(2^n) partitions each of which contains (2^n) pointers. */ +/* In LZRW3-A, the hash function hashes to a partition number. */ +/* */ +/* During the processing of each phrase, LZRW3 overwrites the pointer in the */ +/* position selected by the hash function. LZRW3-A overwrites one of the */ +/* pointers in the partition that was selected by the hash function. */ +/* */ +/* When searching for a match, LZRW3-A matches against all (2^n) strings */ +/* pointed to by the pointers in the target partition. */ +/* */ +/* Deep hash tables were used in early versions of LZRW1 in late 1989, but */ +/* were discarded in an effort to increase speed (which was the primary */ +/* requirement for LZRW1). They were revived for use in LZRW3-A in order to */ +/* produce an algorithm with compression performance competitive with Unix */ +/* compress. */ +/* */ +/* Until 14-Jul-1991, deep hash tables used in prototype LZRW* algorithms */ +/* used a queue discipline within each partition. Upon the arrival of a new */ +/* pointer, the pointers in the partition would be block copied back one */ +/* position (with the oldest pointer being overwritten) and the new pointer */ +/* being inserted in the space at the front (the youngest position). */ +/* This meant that pointers to the (2^n) most recent phrases corresponding to */ +/* each hash was kept. The only flaw in this system was the time-consuming */ +/* block copy operation which was cheap for shallow tables but expensive for */ +/* deep tables. */ +/* */ +/* The traditional solution to ring buffer block copy problems is to maintain */ +/* a cyclic counter which points to the "head" of the queue. However, this */ +/* would have required one counter to be stored for each partition and would */ +/* have been slightly messy. After some thought (on 14-Jul-1991) a better */ +/* solution was found. Instead of maintaining a counter for each partition, */ +/* LZRW3-A maintains a single counter for all partitions! This counter is */ +/* maintained in both the compressor and decompressor and means that the */ +/* algorithm (effectively) overwrites a RANDOM element of the partition to be */ +/* updated. The result was to increase the speed of the compressor and */ +/* decompressor, to make the decompressor's speed independent from whatever */ +/* depth was selected, and to impair compression by less than 1% absolute. */ +/* */ +/* Setting the depth is a speed/compression tradeoff. The table below gives */ +/* the tradeoff observed for a typical 50K text file on a Mac-SE. */ +/* Note: %Rem=Percentage Remaining (after compression). */ +/* */ +/* Depth %Rem CmpK/s DecK/s */ +/* 1 45.2 14.77 32.24 */ +/* 2 42.6 12.12 31.26 */ +/* 4 40.9 10.28 31.91 */ +/* 8 40.0 7.81 32.36 */ +/* 16 39.5 5.30 32.47 */ +/* 32 39.0 3.23 32.59 */ +/* */ +/* I have chosen a depth of 8 as the "default" depth for LZRW3-A. If you use */ +/* a depth different to this (e.g. 4), you should use the name LZRW3-A(4) to */ +/* indicate that a different depth is being used. LZRW3-A(8) is an acceptable */ +/* longhand for LZRW3-A. */ +/* */ +/* To change the depth, search for "HERE IT IS" in the rest of this file. */ +/* */ +/* +---+ */ +/* |___|4095 */ +/* |===| */ +/* +---------------------*_|<---+ /----+---\ */ +/* | |___| +---|Hash | */ +/* | 512 partitions |___| |Function| */ +/* | of 8 pointers |===| \--------/ */ +/* | each (or any |___|0 ^ */ +/* | a*b=4096) +---+ | */ +/* | Hash +-----+ */ +/* | Table | */ +/* | --- */ +/* v ^^^ */ +/* +-------------------------------------|----------------+ */ +/* |||||||||||||||||||||||||||||||||||||||||||||||||||||||| */ +/* +-------------------------------------|----------------+ */ +/* | |1......18| | */ +/* |<------- Lempel=History ------------>|<--Ziv-->| | */ +/* | (=bytes already processed) |<-Still to go-->| */ +/* |<-------------------- INPUT BLOCK ------------------->| */ +/* */ +/* */ +/******************************************************************************/ +/* */ +/* DEFINITION OF COMPRESSED FILE FORMAT */ +/* ==================================== */ +/* The file consists of zero */ +/* or more GROUPS, each of which represents one or more bytes. */ +/* * Each group consists of two bytes of CONTROL information followed by */ +/* sixteen ITEMs except for the last group which can contain from one */ +/* to sixteen items. */ +/* * An item can be either a LITERAL item or a COPY item. */ +/* * Each item corresponds to a bit in the control bytes. */ +/* * The first control byte corresponds to the first 8 items in the group */ +/* with bit 0 corresponding to the first item in the group and bit 7 to */ +/* the eighth item in the group. */ +/* * The second control byte corresponds to the second 8 items in the group */ +/* with bit 0 corresponding to the ninth item in the group and bit 7 to */ +/* the sixteenth item in the group. */ +/* * A zero bit in a control word means that the corresponding item is a */ +/* literal item. A one bit corresponds to a copy item. */ +/* * A literal item consists of a single byte which represents itself. */ +/* * A copy item consists of two bytes that represent from 3 to 18 bytes. */ +/* * The first byte in a copy item will be denoted C1. */ +/* * The second byte in a copy item will be denoted C2. */ +/* * Bits will be selected using square brackets. */ +/* For example: C1[0..3] is the low nibble of the first control byte. */ +/* of copy item C1. */ +/* * The LENGTH of a copy item is defined to be C1[0..3]+3 which is a number */ +/* in the range [3,18]. */ +/* * The INDEX of a copy item is defined to be C1[4..7]*256+C2[0..8] which */ +/* is a number in the range [0,4095]. */ +/* * A copy item represents the sequence of bytes */ +/* text[POS-OFFSET..POS-OFFSET+LENGTH-1] where */ +/* text is the entire text of the uncompressed string. */ +/* POS is the index in the text of the character following the */ +/* string represented by all the items preceeding the item */ +/* being defined. */ +/* OFFSET is obtained from INDEX by looking up the hash table. */ +/* */ +/******************************************************************************/ + +/* When I first started to get concerned about the portability of my C code, */ +/* I switched over to using only macro defined types UBYTE, UWORD, ULONG and */ +/* one or two others. While, these are useful for most purposes, they impair */ +/* efficiency as, if I have a variable whose range will be [0,1000], I will */ +/* declare it as a UWORD. This will translate into (say) "short int" and */ +/* hence may be less efficient than just an "int" which represents the */ +/* natural size of the machine. Before releasing LZRW3-A, I realized this */ +/* mistake. Unfortunately, I can't access the ftp archive with my portability */ +/* header in it in time for this algorithm's release and so I am including an */ +/* extra definition. The definition UCARD stands for an unsigned (cardinal) */ +/* type that can hold values in the range [0,32767]. This is within the ANSI */ +/* range of a standard int or unsigned. No assumption about overflow of this */ +/* type is made in the code (i.e. all usages are within range and I do not */ +/* use the value -1 to detect the end of loops.). */ +/* You can use either "unsigned" or just "int" here depending on which is */ +/* more efficient in your environment (both the same probably). */ +#define UCARD unsigned + +/* The following constant defines the maximum length of an uncompressed item. */ +/* This definition must not be changed; its value is hardwired into the code. */ +/* The longest number of bytes that can be spanned by a single item is 18 */ +/* for the longest copy item. */ +#define MAX_RAW_ITEM (18) + +/* The following constant defines the maximum length of a compressed group. */ +/* This definition must not be changed; its value is hardwired into the code. */ +/* A compressed group consists of two control bytes followed by up to 16 */ +/* compressed items each of which can have a maximum length of two bytes. */ +#define MAX_CMP_GROUP (2+16*2) + +/* This constant defines the number of pointers in the hash table. The number */ +/* of partitions multiplied by the number of pointers in each partition must */ +/* multiply out to this value of 4096. In LZRW1, LZRW1-A, and LZRW2, this */ +/* table length value can be changed. However, in LZRW3-A (and LZRW3), the */ +/* table length cannot be changed because it is connected directly to the */ +/* coding scheme which is hardwired (the table index of a single pointer is */ +/* transmitted in the 12-bit index field). So don't change this constant! */ +#define HASH_TABLE_LENGTH (4096) + +/* HERE IT IS: THE PLACE TO CHANGE THE HASH TABLE DEPTH! */ +/* The following definition is the log_2 of the depth of the hash table. This */ +/* constant can be in the range [0,1,2,3,...,12]. Increasing the depth */ +/* increases compression at the expense of speed. However, you are not likely */ +/* to see much of a compression improvement (e.g. not more than 0.5%) above a */ +/* value of 6 and the algorithm will start to get very slow. See the table in */ +/* the earlier comments block for an idea of the trade-off involved. */ +/* Note: The parentheses are to avoid macro substitution funnies. */ +/* Note: The LZRW3-A default is a value of (3). */ +/* Note: If you end up choosing a value of 0, you should use LZRW3 instead. */ +/* Note: Changing the value of HASH_TABLE_DEPTH_BITS is the ONLY thing you */ +/* have to do to change the depth, so go ahead and recompile now! */ +/* Note: I have tested LZRW3-A for DEPTH_BITS=0,1,2,3,4 and a few other */ +/* values. However, I have not tested it for 12 as I can't wait that long! */ +#define HASH_TABLE_DEPTH_BITS (3) /* Must be in range [0,12]. */ + +/* The following definitions are all self-explanatory and follow from the */ +/* definition of HASH_TABLE_DEPTH_BITS and the hardwired requirement that the */ +/* hash table contain exactly 4096 pointers. */ +#define PARTITION_LENGTH_BITS (12-HASH_TABLE_DEPTH_BITS) +#define PARTITION_LENGTH (1<>4) & HASH_MASK) \ + << HASH_TABLE_DEPTH_BITS \ + ) + +/* Another operation that is performed more than once is the updating of the */ +/* hash table. Here two macros are defined to simplify update operations. */ +/* Updating consists of identifying and overwriting a pointer in a partition */ +/* with a newer pointer and then updating the global cycle value. */ +/* These macros accept the new pointer (NEWPTR) and either a pointer to */ +/* (P_BASE) or the index of (I_BASE) the zeroth (first, or base) pointer in */ +/* the partition that is to be updated. The macros use the 'cycle' variable */ +/* to locate and overwrite a pointer and then update the cycle value. */ +/* Note: Hardcoding 'cycle' in this macro is naughty (it should really be a */ +/* macro parameter), but I have done so because it neatens up the code. */ +#define UPDATE_P(P_BASE,NEWPTR) \ +{(P_BASE)[cycle++]=(NEWPTR); cycle&=DEPTH_MASK;} + +#define UPDATE_I(I_BASE,NEWPTR) \ +{hash[(I_BASE)+cycle++]=(NEWPTR); cycle&=DEPTH_MASK;} + +/* This constant supplies a legal (in-range) hash table index for use when */ +/* a legal-but-don't-care index is required. */ +#define ANY_HASH_INDEX (0) + +/******************************************************************************/ +UBYTE *p_wrk_mem; + +EXPORT int ilzrw3a(void *mem_start) +{ +p_wrk_mem = mem_start; +return MEM_REQ; +} + +EXPORT void wlzrw3a + (p_src_first,src_len,p_dst_first,p_dst_len) +/* Input : Specify input block using p_src_first and src_len. */ +/* Input : Point p_dst_first to the start of the output zone (OZ). */ +/* Input : Point p_dst_len to a ULONG to receive the output length. */ +/* Input : Input block and output zone must not overlap. */ +/* Output : Length of output block written to *p_dst_len. */ +/* Output : Output block in Mem[p_dst_first..p_dst_first+*p_dst_len-1]. May */ +/* Output : write in OZ=Mem[p_dst_first..p_dst_first+src_len+MAX_CMP_GROUP-1].*/ +/* Output : Upon completion *p_dst_len contains final size or 0 */ +UBYTE *p_src_first; +ULONG src_len; +UBYTE *p_dst_first; +ULONG *p_dst_len; +{ + /* p_src and p_dst step through the source and destination blocks. */ + UBYTE *p_src = p_src_first; + UBYTE *p_dst = p_dst_first; + + /* The following variables are never modified and are used in the */ + /* calculations that determine when the main loop terminates. */ + UBYTE *p_src_post = p_src_first+src_len; + UBYTE *p_dst_post = p_dst_first+*p_dst_len; + UBYTE *p_src_max1 = p_src_first+src_len-MAX_RAW_ITEM; + UBYTE *p_src_max16 = p_src_first+src_len-MAX_RAW_ITEM*16; + + /* The variables 'p_control' and 'control' are used to buffer control bits. */ + /* Before each group is processed, the next two bytes of the output block */ + /* are set aside for the control word for the group about to be processed. */ + /* 'p_control' is set to point to the first byte of that word. Meanwhile, */ + /* 'control' buffers the control bits being generated during the processing */ + /* of the group. Instead of having a counter to keep track of how many items */ + /* have been processed (=the number of bits in the control word), at the */ + /* start of each group, the top word of 'control' is filled with 1 bits. */ + /* As 'control' is shifted for each item, the 1 bits in the top word are */ + /* absorbed or destroyed. When they all run out (i.e. when the top word is */ + /* all zero bits, we know that we are at the end of a group. */ + #define TOPWORD 0xFFFF0000 + UBYTE *p_control; + ULONG control=TOPWORD; + + /* The variable 'hash' always points to the first element of the hash table. */ + UBYTE **hash= (UBYTE **) p_wrk_mem; + + /* The following two variables represent the literal buffer. p_h1 points to */ + /* the partition (i.e. the zero'th (first) element of the partition) */ + /* corresponding to the youngest literal. p_h2 points to the partition */ + /* corresponding to the second youngest literal. */ + /* The value zero denotes an "empty" buffer value with p_h1=0 => p_h2=0. */ + UBYTE **p_h1=0; + UBYTE **p_h2=0; + + /* The following variable holds the current 'cycle' value. This value cycles */ + /* through the range [0,HASH_TABLE_DEPTH-1], being incremented every time */ + /* the hash table is updated. The value gives the within-partition number of */ + /* the next pointer to be overwritten. The decompressor maintains a cycle */ + /* value in synchrony. */ + UCARD cycle=0; + + /* Reserve the first word of output as the control word for the first group. */ + /* Note: This is undone at the end if the input block is empty. */ + p_control=p_dst; p_dst+=2; + + /* Initialize all elements of the hash table to point to a constant string. */ + /* Use of an unrolled loop speeds this up considerably. */ + /* These variables should really be declared "register", but I am worried */ + /* about the possibility that extra register declarations will tempt stupid */ + /* compilers to allocate all registers before they get to the innermostloop. */ + {UCARD i; UBYTE **p_h=hash; + #define ZH *p_h++=START_STRING_18 + for (i=0;i<256;i++) /* 256=HASH_TABLE_LENGTH/16. */ + {ZH;ZH;ZH;ZH; + ZH;ZH;ZH;ZH; + ZH;ZH;ZH;ZH; + ZH;ZH;ZH;ZH;} + } + + /* The main loop processes either 1 or 16 items per iteration. As its */ + /* termination logic is complicated, I have opted for an infinite loop */ + /* structure containing 'break' and 'goto' statements. */ + while (TRUE) + {/* Begin main processing loop. */ + + /* Note: All the variables here except unroll should be defined within */ + /* the inner loop. Unfortunately the loop hasn't got a block. */ + UBYTE *p_ziv; /* Points to first byte of current Ziv. */ + UCARD unroll; /* Loop counter for unrolled inner loop. */ + UCARD index; /* Index of current partition. */ + UBYTE **p_h0; /* Pointer to current partition. */ + register UCARD d; /* Depth looping variable. */ + register UCARD bestlen; /* Holds the best length seen so far. */ + register UCARD bestpos; /* Holds number of best pointer seen so far. */ + + /* Test for overrun and jump to overrun code if necessary. */ + if (p_dst>p_dst_post) + goto overrun; + + /* The following cascade of if statements efficiently catches and deals */ + /* with varying degrees of closeness to the end of the input block. */ + /* When we get very close to the end, we stop updating the table and */ + /* code the remaining bytes as literals. This makes the code simpler. */ + unroll=16; + if (p_src>p_src_max16) + { + unroll=1; + if (p_src>p_src_max1) + { + if (p_src==p_src_post) + break; + else + {p_h0=&hash[ANY_HASH_INDEX]; /* Avoid undefined pointer. */ + goto literal;} + } + } + + /* This inner unrolled loop processes 'unroll' (whose value is either 1 */ + /* or 16) items. I have chosen to implement this loop with labels and */ + /* gotos to heighten the ease with which the loop may be implemented with */ + /* a single decrement and branch instruction in assembly language and */ + /* also because the labels act as highly readable place markers. */ + /* (Also because we jump into the loop for endgame literals (see above)). */ + + begin_unrolled_loop: + + p_ziv=p_src; + + /* To process the next phrase, we hash the next three bytes to obtain */ + /* an index to the zeroth (first) pointer in a target partition. We */ + /* get the pointer. */ + index=HASH(p_src); + p_h0=&hash[index]; + + /* This next part runs through the pointers in the partition matching */ + /* the bytes they point to in the Lempel with the bytes in the Ziv. */ + /* The length (bestlen) and within-partition pointer number (bestpos) */ + /* of the longest match so far is maintained and is the output of this */ + /* segment of code. The s[bestlen]==... is an optimization only. */ + bestlen=0; + bestpos=0; + for (d=0;dbestlen) + { + bestpos=d; + bestlen=len; + } + } + } + + /* The length of the longest match determines whether we code a */ + /* literal item or a copy item. */ + + if (bestlen<3) + { + /* Literal. */ + + /* Code the literal byte as itself and a zero control bit. */ + literal: *p_dst++=*p_src++; control&=0xFFFEFFFF; + + /* We have just coded a literal. If we had two pending ones, that */ + /* makes three and we can update the hash table. */ + if (p_h2!=0) + {UPDATE_P(p_h2,p_ziv-2);} + + /* In any case, rotate the hash table pointers for next time. */ + p_h2=p_h1; p_h1=p_h0; + + } + else + { + /* Copy */ + + /* To code a copy item, we construct a hash table index of the */ + /* winning pointer (index+=bestpos) and code it and the best length */ + /* into a 2 byte code word. Bump up p_src. */ + index+=bestpos; + *p_dst++=((index&0xF00)>>4)|(bestlen-3); + *p_dst++=index&0xFF; + p_src+=bestlen; + + /* As we have just coded three bytes, we are now in a position to */ + /* update the hash table with the literal bytes that were pending */ + /* upon the arrival of extra context bytes. */ + if (p_h1!=0) + { + if (p_h2!=0) + {UPDATE_P(p_h2,p_ziv-2); p_h2=0;} + UPDATE_P(p_h1,p_ziv-1); p_h1=0; + } + + /* In any case, we can update the hash table based on the current */ + /* position as we just coded at least three bytes in a copy items. */ + UPDATE_P(p_h0,p_ziv); + } + control>>=1; + + /* This loop is all set up for a decrement and jump instruction! */ + if (--unroll) goto begin_unrolled_loop; + + /* At this point it will nearly always be the end of a group in which */ + /* case, we have to do some control-word processing. However, near the */ + /* end of the input block, the inner unrolled loop is only executed once. */ + /* This necessitates the 'if' test. */ + if ((control&TOPWORD)==0) + { + /* Write the control word to the place we saved for it in the output. */ + *p_control++= control &0xFF; + *p_control = (control>>8) &0xFF; + + /* Reserve the next word in the output block for the control word */ + /* for the group about to be processed. */ + p_control=p_dst; p_dst+=2; + + /* Reset the control bits buffer. */ + control=TOPWORD; + } + + } /* End main processing loop. */ + + /* After the main processing loop has executed, all the input bytes have */ + /* been processed. However, the control word has still to be written to the */ + /* word reserved for it in the output at the start of the most recent group. */ + /* Before writing, the control word has to be shifted so that all the bits */ + /* are in the right place. The "empty" bit positions are filled with 1s */ + /* which partially fill the top word. */ + while(control&TOPWORD) control>>=1; + *p_control++= control &0xFF; + *p_control++=(control>>8) &0xFF; + + /* If the last group contained no items, delete the control word too. */ + if (p_control==p_dst) p_dst-=2; + + /* Write the length of the output block to the dst_len parameter and return. */ + *p_dst_len=p_dst-p_dst_first; + return; + + /* Jump here as soon as an overrun is detected. An overrun is defined to */ + /* have occurred if p_dst>p_dst_first+*p_dst_len as set by caller. */ + /* The algorithm checks for overruns at least at the end of each group */ + /* which means that the maximum overrun is MAX_CMP_GROUP bytes. */ + /* Once an overrun occurs, the only thing to do is to return an error */ + overrun: + *p_dst_len=0; +} + +/******************************************************************************/ + +EXPORT int rlzrw3a + (p_src_first, p_dst, dst_len) +/* Input : Specify input block using p_src_first. */ +/* Input : Point p_dst to the start of the output zone. */ +/* Input : dst_len contains output length */ +/* Input : Input block and output zone must not overlap. User knows */ +/* Input : upperbound on output block length from earlier compression. */ +/* Input : In any case, maximum expansion possible is nine times. */ +/* Output : Length of output block written to *p_dst_len. */ +/* Output : Output block in Mem[p_dst..p_dst+dst_len-1]. */ +/* Output : Writes only in Mem[p_dst..p_dst+dst_len-1]. */ +UBYTE *p_src_first; +UBYTE *p_dst; +ULONG dst_len; +{ + /* Byte pointers scan through the input and output blocks. */ + register UBYTE *p_src = p_src_first; + + /* The following two variables are never modified and are used to control */ + /* the main loop. */ + UBYTE *p_dst_post = p_dst+dst_len; + UBYTE *p_dst_max16 = p_dst+dst_len-MAX_RAW_ITEM*16; + + /* The hash table is the only resident of the working memory. The hash table */ + /* contains HASH_TABLE_LENGTH=4096 pointers to positions in the history. To */ + /* keep Macintoshes happy, it is longword aligned. */ + UBYTE **hash = (UBYTE **) p_wrk_mem; + + /* The variable 'control' is used to buffer the control bits which appear in */ + /* groups of 16 bits (control words) at the start of each compressed group. */ + /* When each group is read, bit 16 of the register is set to one. Whenever */ + /* a new bit is needed, the register is shifted right. When the value of the */ + /* register becomes 1, we know that we have reached the end of a group. */ + /* Initializing the register to 1 thus instructs the code to follow that it */ + /* should read a new control word immediately. */ + register ULONG control=1; + + /* The value of 'literals' is always in the range 0..3. It is the number of */ + /* consecutive literal items just seen. We have to record this number so as */ + /* to know when to update the hash table. When literals gets to 3, there */ + /* have been three consecutive literals and we can update at the position of */ + /* the oldest of the three. */ + register UCARD literals=0; + + /* The following variable holds the current 'cycle' value. This value cycles */ + /* through the range [0,HASH_TABLE_DEPTH-1], being incremented every time */ + /* the hash table is updated. The value give the within-partition number of */ + /* the next pointer to be overwritten. The compressor maintains a cycle */ + /* value in synchrony. */ + UCARD cycle=0; + + /* Initialize all elements of the hash table to point to a constant string. */ + /* Use of an unrolled loop speeds this up considerably. */ + /* The comment about register declarations above similar code in the */ + /* compressor applies here too. */ + {UCARD i; UBYTE **p_h=hash; + #define ZJ *p_h++=START_STRING_18 + for (i=0;i<256;i++) /* 256=HASH_TABLE_LENGTH/16. */ + {ZJ;ZJ;ZJ;ZJ; + ZJ;ZJ;ZJ;ZJ; + ZJ;ZJ;ZJ;ZJ; + ZJ;ZJ;ZJ;ZJ;} + } + + /* The outer loop processes either 1 or 16 items per iteration depending on */ + /* how close p_dst is to the end of the output block. */ + while (p_dst!=p_dst_post) + {/* Start of outer loop */ + + register UCARD unroll; /* Counts unrolled loop executions. */ + + /* When 'control' has the value 1, it means that the 16 buffered control */ + /* bits that were read in at the start of the current group have all been */ + /* shifted out and that all that is left is the 1 bit that was injected */ + /* into bit 16 at the start of the current group. When we reach the end */ + /* of a group, we have to load a new control word and inject a new 1 bit. */ + if (control==1) + { + control=0x10000|*p_src++; + control|=(*p_src++)<<8; + } + + /* If it is possible that we are within 16 groups from the end of the */ + /* input, execute the unrolled loop only once, else process a whole group */ + /* of 16 items by looping 16 times. */ + unroll= p_dst<=p_dst_max16 ? 16 : 1; + + /* This inner loop processes one phrase (item) per iteration. */ + while (unroll--) + { /* Begin unrolled inner loop. */ + + /* Process a literal or copy item depending on the next control bit. */ + if (control&1) + { + /* Copy item. */ + + register UBYTE *p; /* Points to place from which to copy. */ + register UCARD lenmt; /* Length of copy item minus three. */ + register UBYTE *p_ziv=p_dst; /* Pointer to start of current Ziv. */ + register UCARD index; /* Index of hash table copy pointer. */ + + /* Read and dismantle the copy word. Work out from where to copy. */ + lenmt=*p_src++; + index=((lenmt&0xF0)<<4)|*p_src++; + p=hash[index]; + lenmt&=0xF; + + /* Now perform the copy using a half unrolled loop. */ + *p_dst++=*p++; + *p_dst++=*p++; + *p_dst++=*p++; + while (lenmt--) + *p_dst++=*p++; + + /* Because we have just received 3 or more bytes in a copy item */ + /* (whose bytes we have just installed in the output), we are now */ + /* in a position to flush all the pending literal hashings that had */ + /* been postponed for lack of bytes. */ + if (literals>0) + { + register UBYTE *r=p_ziv-literals;; + UPDATE_I(HASH(r),r); + if (literals==2) + {r++; UPDATE_I(HASH(r),r);} + literals=0; + } + + /* In any case, we can immediately update the hash table with the */ + /* current position. We don't need to do a HASH(...) to work out */ + /* where to put the pointer, as the compressor just told us!!! */ + UPDATE_I(index&(~DEPTH_MASK),p_ziv); + } + else + { + /* Literal item. */ + + /* Copy over the literal byte. */ + *p_dst++=*p_src++; + + /* If we now have three literals waiting to be hashed into the hash */ + /* table, we can do one of them now (because there are three). */ + if (++literals == 3) + {register UBYTE *p=p_dst-3; + UPDATE_I(HASH(p),p); literals=2;} + } + + /* Shift the control buffer so the next control bit is in bit 0. */ + control>>=1; + + } /* End unrolled inner loop. */ + + } /* End of outer loop */ + return (p_src-p_src_first); +} + +/******************************************************************************/ +/* End of LZRW3-A.C */ +/******************************************************************************/ + --- linux/drivers/block/lzv.c~ Tue May 31 15:22:53 1994 +++ linux/drivers/block/lzv.c Tue May 31 15:22:53 1994 @@ -0,0 +1,209 @@ +/*********************************************************************** +** +** lzv.c -- an extremly fast compression/decompression-method +** +** Written by Hermann Vogt +** +** v 0.3 -- 94/03/08 aCembler version of rLZV built in. +** v 0.2 -- 94/03/04 Changes for usage with DouBle 0.2 built in. +** v 0.1 -- 94/03/01 Intensivly tested, removed all known bugs. +** v 0.0 -- 94/02/21 First Version. +** +** Copyright (c) 1994 Hermann Vogt. Redistribution of this file is +** permitted under the GNU Public Licence. +** +** The method presented here is faster and compresses better +** than lzrw1 and lzrw1-a. I named it lzv for "Lev-Zimpel-Vogt". +** It uses ideas introduced by Ross Williams in his algorithm lzrw1 +** [R. N. Williams (1991): "An Extremly Fast ZIV-Lempel Data +** Compression Algorithm", Proceedings IEEE Data Compression +** Conference, Snowbird, Utah, 362-371] and by Fiala and Green in their +** algorithm a1 [E. R. Fiala, D. H. Greene (1989): "Data Compression +** with Finite Windows", Communications of the ACM, 4, 490-505]. +** Because lzv differs strongly from both, I hope there will be no +** patent problems. The hashing-method has been stolen from Jean-loup +** Gailly's (patent free) gzip. +** +** KNOWN PROBLEMS: +** - My english is very bad. +** - Badly commented. (I hope this will be better in the next +** version.) +** - I'm not sure if lzv is free from patent problems. +** +***********************************************************************/ + +#define MLL 32 /* Maximum len of chain of literals */ +#define MML (8+256) /* Maximum len of match */ +#define MOFF 8191 /* Maximum offset */ +#define HSIZ 32768 /* Size of Hashtable */ + +typedef unsigned char uch; +typedef unsigned short ush; +typedef unsigned int uit; + +static ush *htab; + +void +wLZV(uch *in, uch *out, int len, int *out_len) +{ + uit hval, op, ip, l_len, m_pos, m_off, m_len, maxlen; + + maxlen = *out_len; + *out_len = 0; + hval = ((in[0] << 5) ^ in[1]) & (HSIZ - 1); + ip = op = l_len = 0; + do { + hval = ((hval << 5) ^ in[ip+2]) & (HSIZ - 1); + m_pos = htab[hval]; + htab[hval] = ip; + if (m_pos < ip && + in[m_pos] == in[ip] && + (m_off = ip - m_pos - 1) <= MOFF && + ip + 4 < len && + *(ush *)(in+m_pos+1) == *(ush *)(in+ip+1)) { + /* We have found a match */ + uit look = len - ip - 2; + if (look > MML) look = MML; + m_len = 2; + do { + m_len++; + } while(m_len != look && in[ip+m_len] == in[m_pos+m_len]); + + if (op + 2 + l_len + 3 >= maxlen) return; + if (l_len != 0) { + out[op++] = (l_len - 1) << 3; + do { + out[op++] = in[ip-l_len--]; + } while (l_len != 0); + } + m_len -= 2; + if (m_len <= 6) { + out[op++] = m_len | ((m_off >> 5) & 0xf8); + } + else { + out[op++] = 0x07 | ((m_off >> 5) & 0xf8); + out[op++] = m_len - 7; + } + out[op++] = m_off & 0xff; + ip++; + hval = ((hval << 5) ^ in[ip+2]) & (HSIZ - 1); + htab[hval] = ip; + ip++; + do { + hval = ((hval << 5) ^ in[ip+2]) & (HSIZ - 1); + htab[hval] = ip; + ip++; + m_len--; + } while (0 != m_len); + } + else { + /* No match found */ + ip++; + l_len++; + if (MLL == l_len) { + if (op + 2 + MLL >= maxlen) return; + out[op++] = 0xf8; + do { + out[op++] = in[ip-l_len--]; + } while (l_len != 0); + } + } + } while (ip < len); + if (l_len != 0) { + if (op + l_len + 3 >= maxlen) return; + out[op++] = (l_len - 1) << 3; + do { + out[op++] = in[ip-l_len--]; + } while (l_len != 0); + } + *out_len = op; + return; +} + +#if defined(LZV_NOASM) + +int +rLZV(uch *in, uch *op, int len) +{ + uit tbuf, c_len; + uch *ip, *m_pos, *out_end; + + ip = in; + out_end = op + len; + do { + tbuf = *ip++; + c_len = tbuf & 0x07; + if (0 == c_len) { + c_len = (tbuf >> 3) + 1; + do { + *op++ = *ip++; + c_len--; + } while (0 != c_len); + } + else { + if (0x07 == c_len) c_len = *ip++ + 7; + m_pos = op - 1 - (((uit) (tbuf & 0xf8) << 5) | *ip++); + *op++ = *m_pos++; + *op++ = *m_pos++; + do { + *op++ = *m_pos++; + c_len--; + } while (0 != c_len); + } + } while (op < out_end); + return (ip-in); +} + +#else + +/* +** aCembler version +** +** IMPORTANT: Use gcc -O2 -fomit-frame-pointer!!! +*/ + +int +rLZV(uch *in, uch *out, int len) +{ + register uit tbuf; + register uch *ip; + register uch *op asm ("%edi"); + register uch *m_pos asm ("%esi"); + uch *out_end; + register uit c_len asm ("%ecx"); + + ip = in; + op = out; + out_end = out + len; + asm volatile ("cld"); + do { + tbuf = *ip++; + c_len = tbuf & 0x07; + if (0 == c_len) { + c_len = (tbuf >> 3) + 1; + m_pos = ip; + ip += c_len; + asm volatile ("rep; movsb" + : /* no output */ + : "g" (m_pos), "g" (op), "g" (c_len)); + } + else { + if (0x07 == c_len) c_len = *ip++ + 9; + else c_len += 2; + m_pos = op - 1 - (((uit) (tbuf & 0xf8) << 5) | *ip++); + asm volatile ("rep; movsb" + : /* no output */ + : "g" (m_pos), "g" (op), "g" (c_len)); + } + } while (op < out_end); + return (ip-in); +} + +#endif + +int +iLZV(void *mem_start) +{ + htab = (ush *) mem_start; + return HSIZ*sizeof(ush); +} --- linux/drivers/block/lzw.c~ Tue May 31 15:22:53 1994 +++ linux/drivers/block/lzw.c Tue May 31 15:22:53 1994 @@ -0,0 +1,298 @@ +/* /linux/drivers/block/lzw.c + * + * Written by Jean-Marc Verbavatz 12 Dec 1993 + * + * 15 Feb 1994: + * String repeat feature added. + */ + +/* LZW Compression and Decompression: + Functions: + RLZW(si, so, len) Decompression + code *si; compressed data + byte *so; buffer for uncompressed data + int len; expected length of uncompressed data + + WLZW(si, so, len, maxlen) Coding + byte *si; raw data + code *so; buffer for compressed data + int len; length of raw data + int maxlen; maximum size of compressed data + (so buffer must be slightly longer than maxlen) + Return code: + 0 = Worthless CPU waste (No compression) + -1 = General error + -2 = Logical error + -3 = Expand error + >0 = OK/total length +*/ +#include + +#define LZSIZE 4096 /* Should stay < 32768 */ +#define CLEAR 256 /* Clear Code */ +#define REPEAT 257 +#define START 258 + +typedef unsigned short code; +typedef unsigned char byte; + +static code Prefix, Prefix0, Index; +static int code_len, new_entry; /* For repeated strings */ +static int bits, off, size; +static code *scode; +static byte *sbyte; +static unsigned int pcode, pbyte, length; + +code *PTable, *NTable; +byte *CTable; + +/* Write Next Code */ +static int WCode(code wcode) +{ +int todo; + +pcode+=bits; +/* Quickly check output buffer size */ +if((pcode>>3) > length) return 0; /* Insufficient compression achieved */ + +if((todo = bits+off-16)>=0) { + *scode++ |= wcode>>todo; + *scode = wcode<<(16-todo); + off = todo; +} else { + *scode |= wcode<<(-todo); + off += bits; +} +return 1; +} + +/* Read Next Code */ +static short RCode(void) +{ +code rcode; /* 15 bits maximum, with LZSIZE=32768; never negative */ +int todo; + +if((todo = bits+off-16)>=0) { + rcode = (*scode++)<>(16-todo); + off = todo; +} else { + rcode = (*scode)>>(-todo); + off += bits; +} +rcode&=size-1; +return (short) rcode; +} + +/* Initialization (R/W) */ +static void InitTable(void) +{ +bits = 8; +size = 256; +pbyte = pcode = off = 0; +Index = START; +memset(PTable, -1, LZSIZE*sizeof(code)); + +} + +/* Initialization for decompression */ +static void RInitTable(void) +{ +int i; +byte *p; + +InitTable(); +for(i = 0, p = CTable; i < CLEAR; i++) + *p++ = i; +} + +/* Lookup Table */ +static code LookUp(byte Car) +{ +code pi; + +pi = PTable[Prefix]; +while(((short)pi) != -1) { + if(CTable[pi] == Car) return pi; + pi = NTable[pi]; +} +return -1; /* No Hit */ +} + +/* byte is added to table and becomes prefix */ +static int WAddPrefix(void) +{ +code pi; + +pi = PTable[Prefix]; +PTable[Prefix] = Index; /* Next entry */ +NTable[Index] = pi; +CTable[Index++] = *sbyte; + +if(Index == LZSIZE) { /* Table full */ + if(!WCode(CLEAR)) return 0; + Index = START; + memset(PTable, -1, LZSIZE*sizeof(code)); + bits = 8; + size = 256; +} else if(Index > size) { + bits++; + size <<= 1; +} +return 1; +} + +static int Expand(code val) +{ +code p,q,r; + +if(val > Index) + return -2; +q = -1; +PTable[Index] = Prefix; +do { + p = val; + while((p = PTable[(r = p)]) != q); /* Get previous */ + *sbyte++ = CTable[r]; + if(++pbyte >= length) return 0; /* Done; skip useless stuff */ + if(((short)q) == -1 && new_entry) { + if(Index == LZSIZE) return -3; + CTable[Index++] = CTable[r]; + new_entry = 0; + } + q = r; +} while(q != val); +Prefix = val; +return 1; +} + +int check_repeat(int len) +{ +int n = 0; +char *s, *s0; + +s = sbyte; /* Current string */ +s0 = s - code_len; /* Reference string */ + +while(code_len <= len && (n+1) < size) { + if(memcmp(s0, s, code_len)) break; + len -= code_len; /* Number of bytes left */ + n++; /* Number of repeats */ + s += code_len; +} +return n; +} + +/* Write Lzw (compression) */ +int WLZW(byte *si, code *so, int len, int maxlen) +{ +code val; +int Repeat; + +scode = so; +*scode = 0; +sbyte = si; +length = maxlen; +InitTable(); + +Prefix = Prefix0 = *sbyte; +code_len = 0; +while(++pbyte 1) { /* at leat 2 bytes */ +/* Check for string repeat. If positive, we are going to write 3 codes. + Therefore, we need to filter small repeats */ + Repeat = check_repeat(len-pbyte); /* Could do better */ + if(Repeat > 3) { /* At least 4 times (1+>3) */ + WCode(REPEAT); + WCode(Repeat); + if(!WCode(Prefix)) return 0; + pbyte += code_len*Repeat; /* Total length of repeat */ + if(pbyte >= len) break; + sbyte += code_len*Repeat; /* position of next byte */ + } + } + if(((short)(val=LookUp(*sbyte)))==-1) { /* Break in sequence */ + if(!WCode(Prefix)) return 0; /* Write to buffer */ + if(!WAddPrefix()) return 0; /* Car is new prefix */ + Prefix = Prefix0 = *sbyte; + code_len = 0; + } else Prefix = val; +} +if(!WCode(Prefix)) return 0; + +len = pcode/sizeof(code)/8; +if(pcode&(sizeof(code)*8-1)) len++; +len *= sizeof(code); +if(len > maxlen) return 0; +return len; +} + +/* CLEAR Code Read */ +static int RClear(void) +{ + +bits = 8; +size = 256; +Prefix = RCode(); +*sbyte++ = Prefix; +if(++pbyte >= length) return 0; +new_entry = 1; +Index = START; +bits++; +size = 512; +return 1; +} + +/* Read Lzw (decompression) */ +int RLZW(code *si, byte *so, int len) +{ +code val; +int n; + +sbyte = so; +scode = si; +length = len; +RInitTable(); + +RClear(); +for(;;) { + val = RCode(); + if(val == CLEAR) { + if(!RClear()) break; + continue; + } + if(val == REPEAT) { + len = RCode(); /* # of repeats */ + val = RCode(); /* code to expand */ + do + n = Expand(val); + while(--len && n > 0); + } else { + n = Expand(val); + if(Index >= size) { + bits++; + size <<= 1; + } + new_entry = 1; /* Add new entry at next code */ + } + if(n < 0) return n; + if(n == 0) break; +} +return (scode-si)*sizeof(code); +} + +int iLZW(void *wrk_mem) +{ +void *mem0; + +mem0 = wrk_mem; +PTable = (code *)wrk_mem; +wrk_mem += LZSIZE*sizeof(code); +NTable = (code *)wrk_mem; +wrk_mem += LZSIZE*sizeof(code); +CTable = (byte *)wrk_mem; +wrk_mem += LZSIZE*sizeof(byte); + +return (int)(wrk_mem-mem0); +} --- linux/drivers/block/pred.c~ Tue May 31 15:22:53 1994 +++ linux/drivers/block/pred.c Tue May 31 15:22:53 1994 @@ -0,0 +1,105 @@ +#ifdef __STDC__ +#endif +#include + /* + * linux/drivers/block/pred.c + * program for Dave Rand's rendition of the predictor algorithm + * Modified for Linux compression driver by: + * peter@fsztmap01.tu-graz.ac.at (Peter Trattler) speed improvement + * (Jean-Marc Verbavatz) + * Updated by: iand@labtam.labtam.oz.au (Ian Donaldson) + * Updated by: Carsten Bormann + * Original : Dave Rand / + */ + + /* The following hash code is the heart of the algorithm: + * It builds a sliding hash sum of the previous 3-and-a-bit characters + * which will be used to index the guess table. + * A better hash function would result in additional compression, + * at the expense of time. + */ + #define TableSize 16384 + #define HASH(x) Hash = ((Hash << 7) ^ (x))&(TableSize-1) + +/* static unsigned short int Hash; */ + static unsigned char *GuessTable; + + int ipred(void *mem_start) + { + GuessTable = (unsigned char *) mem_start; + return TableSize; + } + + void wpred(unsigned char *source, int len, unsigned char *dest, int *maxlen) + { + unsigned char *flagdest, *orgdest, *maxdest, *p; + unsigned char flags; + unsigned int Hash; /* Declared as 32-bit-auto for speed reasons */ + + memset(GuessTable, 0, TableSize); + orgdest = dest; + maxdest = dest+*maxlen; + Hash = 0; + while (dest < maxdest) { + flagdest = dest++; /* All guess wrong initially */ + flags = 0; +#define loop(bit) \ + p = GuessTable + Hash; \ + if(*p == *source) flags |= bit; /* Guess was right */ \ + else { /* Guess was wrong */ \ + *p = *source; \ + *dest++ = *source; \ + } \ + HASH(*source++); \ + if(! --len) goto w_done; + + /* I unrolled the original loop */ + loop (0x01); + loop (0x02); + loop (0x04); + loop (0x08); + loop (0x10); + loop (0x20); + loop (0x40); + loop (0x80); +#undef loop + *flagdest = flags; + } + w_done: + *flagdest = flags; + if(len || dest > maxdest) *maxlen =0; + else *maxlen = (dest - orgdest); + } + + void rpred(unsigned char *source, unsigned char *dest, int len) + { + unsigned char flags; + unsigned int Hash; /* Declared as 32-bit-auto for speed reasons */ + + memset(GuessTable, 0, TableSize); + Hash = 0; + for(;;) { + flags = *source++; +#define loop(bit) \ + if (flags & bit) \ + *dest = GuessTable[Hash]; /* Guess correct */ \ + else { \ + GuessTable[Hash] = *source; /* Guess wrong */ \ + *dest = *source++; /* Read from source */ \ + } \ + HASH(*dest++); \ + if(! --len) return; + + /* I unrolled the original loop */ + loop (0x01); + loop (0x02); + loop (0x04); + loop (0x08); + loop (0x10); + loop (0x20); + loop (0x40); + loop (0x80); +#undef loop + } + } + --- linux/config.in~ Tue May 31 14:30:25 1994 +++ linux/config.in Tue May 31 15:40:18 1994 @@ -11,6 +11,7 @@ bool 'Networking support' CONFIG_NET y bool 'Limit memory to low 16MB' CONFIG_MAX_16M n bool 'System V IPC' CONFIG_SYSVIPC y +bool 'Double device driver' CONFIG_DOUBLE y bool 'Use -m486 flag for 486-specific optimizations' CONFIG_M486 y if [ "$CONFIG_NET" = "y" ]; then @@ -121,6 +122,7 @@ if [ "$CONFIG_INET" = "y" ]; then bool 'NFS filesystem support' CONFIG_NFS_FS n fi +bool 'DOUBLE filesystem support' CONFIG_DBLE_FS y bool 'ISO9660 cdrom filesystem support' CONFIG_ISO9660_FS y bool 'OS/2 HPFS filesystem support (read only)' CONFIG_HPFS_FS n bool 'System V and Coherent filesystem support' CONFIG_SYSV_FS n --- linux/MAGIC~ Tue Jun 7 11:00:09 1994 +++ linux/MAGIC Tue Jun 7 11:00:09 1994 @@ -38,5 +38,6 @@ TTY_LDISC_MAGIC 0x5403 struct tty_ldisc include/linux/tty_ldisc.h SERIAL_MAGIC 0x5301 struct async_struct include/linux/serial.h SLIP_MAGIC 0x5302 struct slip drivers/net/slip.h +DB_MAGIC 0x1647E struct db_header include/linux/double.h