Source Code & Software Patents: A Guide to Software & Internet Patent Litigation for Attorneys & Experts
by Andrew Schulman (http://www.SoftwareLitigationConsulting.com)
Code example for Chapter 1: What’s so special (or not so special) about source code?
Code example: mkndx & find in C
mkndx creates an index of lines of source code; find searches in indices created by mkndx
[TODO: show how to use, what output looks like, what index files look like]
[TODO: use strhash.c below to explain data structures, e.g. linked list, table, etc.; note that VBS and awk code merely assume the presence of associated arrays; strhash.c implements them, and strhash.h provides an interface]
[TODO: link to executable files for Windows, Mac OSX; show portion of disassembly; show portion of hexdump]
========
// ndx.c
// TODO:
// change strhash so val is (void *) to be determined by user
// error if can't open file?
// output current count to stderr
// show ls equiv to "dir /s/b /a-d"
#include <stdlib.h>
#include <stdio.h>
#include "strhash.h"
void fail(char *s) { puts(s); exit(1); }
void *alloc(int size)
{
void *p = calloc(size, 1); // 0-init
if (! p) fail("insufficient memory");
return p;
}
HASHTAB files = (HASHTAB) 0;
int get_files(char *s)
{
static int cnt = 0; // only init once!
int this_cnt = 0; // init each time
char *cmd, *buf;
FILE *f;
if (! files) // one-time init
if (! (files = MakeHashTab()))
fail("Can't create files list");
if (*s == '@')
{
f = fopen(s+1, "r");
if (! f) fail("can't open @file");
}
else
{
cmd = alloc(1024);
cmd[0] = '\0';
strcpy(cmd, "dir /s/b /a-d ");
strcat(cmd, s);
strcat(cmd, " > __tmp.tmp"); // TODO: make temp file
//fprintf(stderr, "get_files: %s\n", cmd);
system(cmd);
free(cmd);
f = fopen("__tmp.tmp", "r");
if (! f) fail("can't open __tmp.tmp");
}
buf = alloc(2048);
while (fgets(buf, 2047, f))
{
if ((! *buf) || (*buf == '#')) // comments in @file
continue;
buf[strlen(buf)-1] = '\0'; // remove \n
cnt++;
this_cnt++;
//fprintf(stderr, "get_files: <%s> [%u]\n", buf, cnt);
SetHashTab(files, buf, cnt); // cnt = fnum
}
fclose(f);
free(buf);
return this_cnt;
}
int print_func(char *s, int count, int val, unsigned *p)
{
if (count == 1)
printf("%u\t%s\t[%u,]\n", count, s, val);
else
{
int i, top;
printf("%u\t%s\t[", count, s);
top = min(50, count);
for (i=0; i<top; i++)
{
printf("%u,", p[i]);
}
printf("]\n");
}
return 1;
}
HASHTAB strings = (HASHTAB) 0;
static int gcnt = 0;
int do_file(char *fname, int count, int fnum, unsigned *p)
{
static int fcnt = 0;
int cnt = 0;
FILE *f;
char *buf;
fcnt++;
fprintf(stderr, "%u (%u%%)\t%s\t%u\n", fcnt,
(100*fcnt) / (1+gcnt), fname, fnum);
printf("%u\t%s\n", fnum, fname);
f = fopen(fname, "r");
// if (! f) fail("can't open file"); // no, keep going
if (! f) { fprintf(stderr, "\nCan't open <%s>\n\n", fname); return 0; }
buf = alloc(10240);
// TODO: need to create temp hashtab, so can do 1 entry per file
// TODO: maybe change MakeHashTab to take param with tab_size, store
while (fgets(buf, 10239, f))
{
char *s = buf;
buf[strlen(buf)-1] = '\0'; // remove \n
while (*s == ' ' || *s == '\t') s++; // remove leading spaces
if (*s)
{
cnt++;
SetHashTab(strings, s, fnum); // will keep count
}
}
fclose(f);
free(buf);
return 1;
}
main(int argc, char *argv[])
{
unsigned i;
if (argc < 2)
fail("usage: ndx [file*.ext or @file]");
for (i=1; i<argc; i++)
gcnt += get_files(argv[i]);
printf("%u files\n", gcnt);
// ForXInHashtab(files, print_func);
puts("Files\n");
strings = MakeHashTab();
ForXInHashtab(files, do_file);
fputs("Generating output...\n", stderr);
puts("\nStrings\n");
ForXInHashtab(strings, print_func);
FreeHashTab(files);
FreeHashTab(strings);
}
==========
strhash.h:
// strhash.h
typedef void *HASHTAB ;
HASHTAB MakeHashTab(void);
void FreeHashTab(HASHTAB hashtab);
void SetHashTab(HASHTAB hashtab, char *s, unsigned val);
int GetHashTab(HASHTAB hashtab, char *s);
typedef int (*FORIN_FUNC)(char *s, int count, unsigned val, unsigned *p);
void ForXInHashtab(HASHTAB hashtab, FORIN_FUNC func);
==========
// strhash.c
// TODO: replace val with count and union of val and void*
// use val when count == 1; in one test (Firefox source), 80% of
// entries appeared only 1x
#include <stdlib.h>
#include <stdio.h>
#include "strhash.h"
typedef struct _node {
struct _node *next;
char *s;
unsigned val;
} NODE;
void _fail(const char *s) { puts(s); exit(1); }
void *my_alloc(int x, int y)
{
void *p = calloc(x,y); // zero init
if (! p)
_fail("Error: insufficient memory");
return p;
}
void insert(NODE **list, char *s, unsigned val)
{
NODE *node;
NODE *l2 = *list;
while (l2)
{
if (strcmp(l2->s, s) == 0) // could do case-insensitive
{
l2->val = val; // took 1 hr. to find bug where omitted this
return; // already in list
}
else
l2 = l2->next;
}
node = (NODE *) my_alloc(1, sizeof(NODE));
node->next = *list;
*list = node;
node->s = my_alloc(1, strlen(s)+1);
strcpy(node->s, s);
node->val = val;
}
int find(NODE *list, char *s)
{
while (list)
{
if (*s == *(list->s))
{
static int num_strcmp = 0;
num_strcmp++;
if ((num_strcmp % 1000000) == 0)
fprintf(stderr, "\n\n!! %u calls to strcmp\n\n\n", num_strcmp);
if (strcmp(list->s, s) == 0)
return list->val;
else
list = list->next;
}
else
list = list->next;
}
return 0; // valid val begins with 1
}
// prime numbers: 9973 11113 13997 16943 18917
// TODO: do TAB_SIZE and hash make sense together?
#define TAB_SIZE 11113
// see http://www.cs.yorku.ca/~oz/hash.html
unsigned long HASH(unsigned char *s)
{
unsigned long hash = 5381;
int c;
while (c = *s++) {
hash = ((hash << 5) + hash) + c;
}
return (hash % TAB_SIZE);
}
NODE **mk_hashtab(void) {
return (NODE **) my_alloc(TAB_SIZE, sizeof(NODE *));
}
HASHTAB MakeHashTab(void) {
return (HASHTAB) mk_hashtab();
}
void FreeHashTab(HASHTAB hashtab) {
free(hashtab);
}
void set(NODE **hashtab, char *s, unsigned val) {
insert(&hashtab[HASH(s)], s, val);
}
void SetHashTab(HASHTAB hashtab, char *s, unsigned val) {
set((NODE**) hashtab, s, val);
}
int get(NODE **hashtab, char *s) {
return find(hashtab[HASH(s)], s);
}
int GetHashTab(HASHTAB hashtab, char *s) {
return get((NODE**)hashtab, s);
}
typedef int (*FORIN_FUNC)(char *s, unsigned val);
void for_in(NODE **hashtab, FORIN_FUNC func)
{
NODE *list;
int i;
for (i=0; i<TAB_SIZE; i++)
{
if (list = hashtab[i])
{
while (list)
{
if (! (*func)(list->s, list->count, list->val, list->p))
return; // done if func returns 0
list = list->next;
}
}
}
}
void ForXInHashtab(HASHTAB hashtab, FORIN_FUNC func)
{
for_in((NODE**) hashtab, func);
}
#ifdef TESTING
int print_func(char *s, unsigned val)
{
printf("%u\t%s\n", val, s);
return 1;
}
main(int argc, char *argv[])
{
NODE **hashtab;
char buf[10240];
int i, cnt=0;
hashtab = mk_hashtab();
while (gets(buf)) // only get up to buf size
{
char *s = buf;
while (*s == ' ' || *s == '\t') s++; // remove leading spaces
if (*s)
set(hashtab, s, ++cnt);
}
for_in(hashtab, print_func);
}
#endif
=======
find.c:
// find.c
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include "strhash.h"
void fail(char *s) { puts(s); exit(1); }
int case_sensitive = 0;
char *strlower(char *s) // not in place; make copy
{
char *s2 = malloc(strlen(s)+1);
char *p;
if (! s2) fail("insufficient memory");
s2[0] = '\0';
strcpy(s2, s); // unsafe
for (p=s2; *p; p++) {
if ((*p >= 'A') && (*p <= 'Z'))
*p = *p += 0x20; // 'a' - 'A'
}
return s2; // caller responsibility to free
}
char *match(char *str1, char *str2)
{
if (case_sensitive)
return strstr(str1, str2);
else
{
static char *s2 = (char *) 0;
char *s1 = strlower(str1);
char *ret;
if (! s2) // one time, not going to change
s2 = strlower(str2);
ret = strstr(s1, s2);
free(s1);
// free(s2);
return ret;
}
}
main(int argc, char *argv[])
{
HASHTAB hashtab;
FILE *f;
char *pat, *ndxfile, *buf, *s;
typedef char *STRING;
STRING arr[3];
int i, cnt;
int in_files = 0, in_strings = 0;
if (argc < 3)
fail("usage: find [pat] [ndxfile]");
pat = argv[1];
printf("pat: <%s>\n", pat);
ndxfile = argv[2];
if (! (f = fopen(ndxfile, "r"))) fail("can't open ndxfile");
if (! (hashtab = MakeHashTab())) fail("can't allocate hashtab");
if (! (buf = calloc(10240, 1))) fail("insufficient memory");
while (fgets(buf, 10239, f))
{
s = buf;
if ((! *s) || (*s == '#') || (*s == '\n')) // comments or blank lines
continue;
s[strlen(s)-1] = '\0'; // remove \n
while (*s == ' ' || *s == '\t') s++; // remove leading spaces
if (! *s)
continue;
if (arr[0] = strtok(s, "\t")) cnt = 1;
if (arr[1] = strtok(NULL, "\t")) cnt = 2;
if (arr[2] = strtok(NULL, "\t")) cnt = 3;
if (cnt == 1)
{
if (strcmp(arr[0], "Files") == 0) // doh, remember match ret 0
{
in_files = 1;
}
else if (strcmp(arr[0], "Strings") == 0)
{
in_files = 0;
in_strings = 1;
fputs("Done with files\n", stderr);
}
}
if (in_files && (cnt == 2)) // TODO: error msg if cnt != 2
{
// TODO: need ability to do val -> str,
// following is hack
// could also use first line with "%u files" to alloc array
char *s = malloc(strlen(arr[1])+1);
if (! s) fail("insufficient memory");
s[0] = '\0';
strcpy(s, arr[1]);
SetHashTab(hashtab, arr[0], (unsigned) s); // not atoi
//SetHashTab(hashtab, arr[1], atoi(arr[0])); //TODO: need ability to do val->str
}
if (in_strings && (cnt == 3) && match(arr[1], pat)) //TODO: err msg if cnt!=3
{
int fcount = atoi(arr[0]);
char *str = arr[1];
char *fnums = arr[2];
int len = strlen(fnums);
int fnum;
if (*fnums == '[') fnums++;
if (fnums[len-2] == ']') fnums[len-2] = '\0' ;
if ((fcount == 1) && (fnums[len-3] == ','))
{
fnums[len-3] = '\0';
printf("%s\n\t%s\n", str, GetHashTab(hashtab, fnums));
}
else if (fcount > 1)
{
char *fnumstr;
printf("%s\n", str);
if (fcount >= 50)
printf("COMMON STRING: in %u files, including:\n", fcount);
fnumstr = strtok(fnums, ",");
do {
printf("\t%s\n", GetHashTab(hashtab, fnumstr));
} while (fnumstr = strtok(NULL, ","));
}
}
}
fclose(f);
free(buf);
}
