1 /* $NetBSD: locate.bigram.c,v 1.12 2009/11/17 18:31:12 drochner Exp $ */ 2 3 /* 4 * Copyright (c) 1989, 1993 5 * The Regents of the University of California. All rights reserved. 6 * 7 * This code is derived from software contributed to Berkeley by 8 * James A. Woods. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 13 * 1. Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution. 18 * 3. Neither the name of the University nor the names of its contributors 19 * may be used to endorse or promote products derived from this software 20 * without specific prior written permission. 21 * 22 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 23 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 24 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 25 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 26 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 27 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 28 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 29 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 30 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 31 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 32 * SUCH DAMAGE. 33 */ 34 35 #include <sys/cdefs.h> 36 #ifndef lint 37 __COPYRIGHT("@(#) Copyright (c) 1989, 1993\ 38 The Regents of the University of California. All rights reserved."); 39 #endif /* not lint */ 40 41 #ifndef lint 42 #if 0 43 static char sccsid[] = "@(#)locate.bigram.c 8.2 (Berkeley) 4/28/95"; 44 #endif 45 __RCSID("$NetBSD: locate.bigram.c,v 1.12 2009/11/17 18:31:12 drochner Exp $"); 46 #endif /* not lint */ 47 48 /* 49 * bigram < text > bigrams 50 * 51 * List bigrams for 'updatedb' script. 52 * Use 'code' to encode a file using this output. 53 */ 54 55 #include <stdio.h> 56 #include <stdlib.h> 57 #include <string.h> 58 #include <sys/param.h> /* for MAXPATHLEN */ 59 60 int main(int, char **); 61 static int compare_bigrams(const void *, const void *); 62 static void add_bigram(u_char, u_char); 63 64 static char buf1[MAXPATHLEN] = " "; 65 static char buf2[MAXPATHLEN]; 66 67 struct bigram { 68 int count; 69 u_char b1, b2; /* needed for final sorting */ 70 }; 71 72 struct bigram bigrams[256 * 256]; 73 74 static void 75 add_bigram(u_char i1, u_char i2) 76 { 77 if (i1 != '\n' && i2 != '\n') 78 bigrams[(i1<<8)+i2].count++; 79 } 80 81 static int 82 compare_bigrams(const void *item1, const void *item2) 83 { 84 const struct bigram *it1=item1, *it2=item2; 85 86 if (it1->count != it2->count) 87 return it2->count - it1->count; 88 else if (it1->b1 != it2->b1) 89 return it2->b1 - it1->b1; 90 else 91 return it2->b2 - it2->b2; 92 } 93 94 int 95 main(int argc, char *argv[]) 96 { 97 char *cp; 98 char *oldpath = buf1, *path = buf2; 99 struct bigram *bg; 100 int i; 101 102 /* initialize bigram array */ 103 memset(bigrams, 0, sizeof(bigrams)); 104 for(i=0; i < 65536; i++) { 105 bigrams[i].b1 = i / 256; 106 bigrams[i].b2 = i % 256; 107 } 108 109 while ( fgets ( path, sizeof(buf2), stdin ) != NULL ) { 110 111 /* skip longest common prefix */ 112 for ( cp = path; *cp == *oldpath; cp++, oldpath++ ) 113 if ( *oldpath == '\0' ) 114 break; 115 116 /* 117 * output post-residue bigrams only 118 */ 119 for(; cp[0] != '\0' && cp[1] != '\0'; cp += 2) 120 add_bigram((u_char)cp[0], (u_char)cp[1]); 121 122 if (path == buf1) /* swap pointers */ 123 path = buf2, oldpath = buf1; 124 else 125 path = buf1, oldpath = buf2; 126 } 127 128 /* sort the bigrams by how many times it appeared and their value */ 129 heapsort((void *)bigrams, 256 * 256, sizeof(struct bigram), 130 compare_bigrams); 131 132 /* write 128 most frequent bigrams out */ 133 bg = bigrams; 134 for (i = 0; i < 128 && bg->count > 0; i++, bg++) { 135 if (bg->b1 != '\0') 136 fputc(bg->b1, stdout); 137 if (bg->b2 != '\0') 138 fputc(bg->b2, stdout); 139 } 140 141 return (0); 142 } 143