+ return big-1;
+ }
+ return Nullch;
+}
+
+/* same as instr but allow embedded nulls */
+
+char *
+ninstr(big, bigend, little, lend)
+register char *big;
+register char *bigend;
+char *little;
+char *lend;
+{
+ register char *s, *x;
+ register int first = *little;
+ register char *littleend = lend;
+
+ if (!first && little > littleend)
+ return big;
+ bigend -= littleend - little++;
+ while (big <= bigend) {
+ if (*big++ != first)
+ continue;
+ for (x=big,s=little; s < littleend; /**/ ) {
+ if (*s++ != *x++) {
+ s--;
+ break;
+ }
+ }
+ if (s >= littleend)
+ return big-1;
+ }
+ return Nullch;
+}
+
+/* reverse of the above--find last substring */
+
+char *
+rninstr(big, bigend, little, lend)
+register char *big;
+char *bigend;
+char *little;
+char *lend;
+{
+ register char *bigbeg;
+ register char *s, *x;
+ register int first = *little;
+ register char *littleend = lend;
+
+ if (!first && little > littleend)
+ return bigend;
+ bigbeg = big;
+ big = bigend - (littleend - little++);
+ while (big >= bigbeg) {
+ if (*big-- != first)
+ continue;
+ for (x=big+2,s=little; s < littleend; /**/ ) {
+ if (*s++ != *x++) {
+ s--;
+ break;
+ }
+ }
+ if (s >= littleend)
+ return big+1;
+ }
+ return Nullch;
+}
+
+unsigned char fold[] = {
+ 0, 1, 2, 3, 4, 5, 6, 7,
+ 8, 9, 10, 11, 12, 13, 14, 15,
+ 16, 17, 18, 19, 20, 21, 22, 23,
+ 24, 25, 26, 27, 28, 29, 30, 31,
+ 32, 33, 34, 35, 36, 37, 38, 39,
+ 40, 41, 42, 43, 44, 45, 46, 47,
+ 48, 49, 50, 51, 52, 53, 54, 55,
+ 56, 57, 58, 59, 60, 61, 62, 63,
+ 64, 'a', 'b', 'c', 'd', 'e', 'f', 'g',
+ 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o',
+ 'p', 'q', 'r', 's', 't', 'u', 'v', 'w',
+ 'x', 'y', 'z', 91, 92, 93, 94, 95,
+ 96, 'A', 'B', 'C', 'D', 'E', 'F', 'G',
+ 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O',
+ 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W',
+ 'X', 'Y', 'Z', 123, 124, 125, 126, 127,
+ 128, 129, 130, 131, 132, 133, 134, 135,
+ 136, 137, 138, 139, 140, 141, 142, 143,
+ 144, 145, 146, 147, 148, 149, 150, 151,
+ 152, 153, 154, 155, 156, 157, 158, 159,
+ 160, 161, 162, 163, 164, 165, 166, 167,
+ 168, 169, 170, 171, 172, 173, 174, 175,
+ 176, 177, 178, 179, 180, 181, 182, 183,
+ 184, 185, 186, 187, 188, 189, 190, 191,
+ 192, 193, 194, 195, 196, 197, 198, 199,
+ 200, 201, 202, 203, 204, 205, 206, 207,
+ 208, 209, 210, 211, 212, 213, 214, 215,
+ 216, 217, 218, 219, 220, 221, 222, 223,
+ 224, 225, 226, 227, 228, 229, 230, 231,
+ 232, 233, 234, 235, 236, 237, 238, 239,
+ 240, 241, 242, 243, 244, 245, 246, 247,
+ 248, 249, 250, 251, 252, 253, 254, 255
+};
+
+static unsigned char freq[] = {
+ 1, 2, 84, 151, 154, 155, 156, 157,
+ 165, 246, 250, 3, 158, 7, 18, 29,
+ 40, 51, 62, 73, 85, 96, 107, 118,
+ 129, 140, 147, 148, 149, 150, 152, 153,
+ 255, 182, 224, 205, 174, 176, 180, 217,
+ 233, 232, 236, 187, 235, 228, 234, 226,
+ 222, 219, 211, 195, 188, 193, 185, 184,
+ 191, 183, 201, 229, 181, 220, 194, 162,
+ 163, 208, 186, 202, 200, 218, 198, 179,
+ 178, 214, 166, 170, 207, 199, 209, 206,
+ 204, 160, 212, 216, 215, 192, 175, 173,
+ 243, 172, 161, 190, 203, 189, 164, 230,
+ 167, 248, 227, 244, 242, 255, 241, 231,
+ 240, 253, 169, 210, 245, 237, 249, 247,
+ 239, 168, 252, 251, 254, 238, 223, 221,
+ 213, 225, 177, 197, 171, 196, 159, 4,
+ 5, 6, 8, 9, 10, 11, 12, 13,
+ 14, 15, 16, 17, 19, 20, 21, 22,
+ 23, 24, 25, 26, 27, 28, 30, 31,
+ 32, 33, 34, 35, 36, 37, 38, 39,
+ 41, 42, 43, 44, 45, 46, 47, 48,
+ 49, 50, 52, 53, 54, 55, 56, 57,
+ 58, 59, 60, 61, 63, 64, 65, 66,
+ 67, 68, 69, 70, 71, 72, 74, 75,
+ 76, 77, 78, 79, 80, 81, 82, 83,
+ 86, 87, 88, 89, 90, 91, 92, 93,
+ 94, 95, 97, 98, 99, 100, 101, 102,
+ 103, 104, 105, 106, 108, 109, 110, 111,
+ 112, 113, 114, 115, 116, 117, 119, 120,
+ 121, 122, 123, 124, 125, 126, 127, 128,
+ 130, 131, 132, 133, 134, 135, 136, 137,
+ 138, 139, 141, 142, 143, 144, 145, 146
+};
+
+void
+fbmcompile(str, iflag)
+STR *str;
+int iflag;
+{
+ register unsigned char *s;
+ register unsigned char *table;
+ register int i;
+ register int len = str->str_cur;
+ int rarest = 0;
+ int frequency = 256;
+
+ str_grow(str,len+258);
+#ifndef lint
+ table = (unsigned char*)(str->str_ptr + len + 1);
+#else
+ table = Null(unsigned char*);
+#endif
+ s = table - 2;
+ for (i = 0; i < 256; i++) {
+ table[i] = len;
+ }
+ i = 0;
+#ifndef lint
+ while (s >= (unsigned char*)(str->str_ptr))
+#endif
+ {
+ if (table[*s] == len) {
+#ifndef pdp11
+ if (iflag)
+ table[*s] = table[fold[*s]] = i;
+#else
+ if (iflag) {
+ int j;
+ j = fold[*s];
+ table[j] = i;
+ table[*s] = i;
+ }
+#endif /* pdp11 */
+ else
+ table[*s] = i;
+ }
+ s--,i++;
+ }
+ str->str_pok |= SP_FBM; /* deep magic */
+
+#ifndef lint
+ s = (unsigned char*)(str->str_ptr); /* deeper magic */
+#else
+ s = Null(unsigned char*);
+#endif
+ if (iflag) {
+ register int tmp, foldtmp;
+ str->str_pok |= SP_CASEFOLD;
+ for (i = 0; i < len; i++) {
+ tmp=freq[s[i]];
+ foldtmp=freq[fold[s[i]]];
+ if (tmp < frequency && foldtmp < frequency) {
+ rarest = i;
+ /* choose most frequent among the two */
+ frequency = (tmp > foldtmp) ? tmp : foldtmp;
+ }
+ }
+ }
+ else {
+ for (i = 0; i < len; i++) {
+ if (freq[s[i]] < frequency) {
+ rarest = i;
+ frequency = freq[s[i]];
+ }
+ }
+ }
+ str->str_rare = s[rarest];
+ str->str_state = rarest;
+#ifdef DEBUGGING
+ if (debug & 512)
+ fprintf(stderr,"rarest char %c at %d\n",str->str_rare, str->str_state);
+#endif
+}
+
+char *
+fbminstr(big, bigend, littlestr)
+unsigned char *big;
+register unsigned char *bigend;
+STR *littlestr;
+{
+ register unsigned char *s;
+ register int tmp;
+ register int littlelen;
+ register unsigned char *little;
+ register unsigned char *table;
+ register unsigned char *olds;
+ register unsigned char *oldlittle;
+
+#ifndef lint
+ if (!(littlestr->str_pok & SP_FBM))
+ return instr((char*)big,littlestr->str_ptr);
+#endif
+
+ littlelen = littlestr->str_cur;
+#ifndef lint
+ if (littlestr->str_pok & SP_TAIL && !multiline) { /* tail anchored? */
+ little = (unsigned char*)littlestr->str_ptr;
+ if (littlestr->str_pok & SP_CASEFOLD) { /* oops, fake it */
+ big = bigend - littlelen; /* just start near end */
+ if (bigend[-1] == '\n' && little[littlelen-1] != '\n')
+ big--;
+ }
+ else {
+ s = bigend - littlelen;
+ if (*s == *little && bcmp(s,little,littlelen)==0)
+ return (char*)s; /* how sweet it is */
+ else if (bigend[-1] == '\n' && little[littlelen-1] != '\n') {
+ s--;
+ if (*s == *little && bcmp(s,little,littlelen)==0)
+ return (char*)s;
+ }
+ return Nullch;
+ }
+ }
+ table = (unsigned char*)(littlestr->str_ptr + littlelen + 1);
+#else
+ table = Null(unsigned char*);
+#endif
+ s = big + --littlelen;
+ oldlittle = little = table - 2;
+ if (littlestr->str_pok & SP_CASEFOLD) { /* case insensitive? */
+ while (s < bigend) {
+ top1:
+ if (tmp = table[*s]) {
+ s += tmp;
+ }
+ else {
+ tmp = littlelen; /* less expensive than calling strncmp() */
+ olds = s;
+ while (tmp--) {
+ if (*--s == *--little || fold[*s] == *little)
+ continue;
+ s = olds + 1; /* here we pay the price for failure */
+ little = oldlittle;
+ if (s < bigend) /* fake up continue to outer loop */
+ goto top1;
+ return Nullch;
+ }
+#ifndef lint
+ return (char *)s;
+#endif
+ }
+ }
+ }
+ else {
+ while (s < bigend) {
+ top2:
+ if (tmp = table[*s]) {
+ s += tmp;
+ }
+ else {
+ tmp = littlelen; /* less expensive than calling strncmp() */
+ olds = s;
+ while (tmp--) {
+ if (*--s == *--little)
+ continue;
+ s = olds + 1; /* here we pay the price for failure */
+ little = oldlittle;
+ if (s < bigend) /* fake up continue to outer loop */
+ goto top2;
+ return Nullch;
+ }
+#ifndef lint
+ return (char *)s;
+#endif
+ }
+ }
+ }
+ return Nullch;
+}
+
+char *
+screaminstr(bigstr, littlestr)
+STR *bigstr;
+STR *littlestr;
+{
+ register unsigned char *s, *x;
+ register unsigned char *big;
+ register int pos;
+ register int previous;
+ register int first;
+ register unsigned char *little;
+ register unsigned char *bigend;
+ register unsigned char *littleend;
+
+ if ((pos = screamfirst[littlestr->str_rare]) < 0)
+ return Nullch;
+#ifndef lint
+ little = (unsigned char *)(littlestr->str_ptr);
+#else
+ little = Null(unsigned char *);
+#endif
+ littleend = little + littlestr->str_cur;
+ first = *little++;
+ previous = littlestr->str_state;
+#ifndef lint
+ big = (unsigned char *)(bigstr->str_ptr);
+#else
+ big = Null(unsigned char*);
+#endif
+ bigend = big + bigstr->str_cur;
+ big -= previous;
+ while (pos < previous) {
+#ifndef lint
+ if (!(pos += screamnext[pos]))
+#endif
+ return Nullch;
+ }
+ if (littlestr->str_pok & SP_CASEFOLD) { /* case insignificant? */
+ do {
+ if (big[pos] != first && big[pos] != fold[first])
+ continue;
+ for (x=big+pos+1,s=little; s < littleend; /**/ ) {
+ if (x >= bigend)
+ return Nullch;
+ if (*s++ != *x++ && fold[*(s-1)] != *(x-1)) {
+ s--;
+ break;
+ }
+ }
+ if (s == littleend)
+#ifndef lint
+ return (char *)(big+pos);
+#else
+ return Nullch;
+#endif
+ } while (
+#ifndef lint
+ pos += screamnext[pos] /* does this goof up anywhere? */
+#else
+ pos += screamnext[0]
+#endif
+ );
+ }
+ else {
+ do {
+ if (big[pos] != first)
+ continue;
+ for (x=big+pos+1,s=little; s < littleend; /**/ ) {
+ if (x >= bigend)
+ return Nullch;
+ if (*s++ != *x++) {
+ s--;
+ break;
+ }
+ }
+ if (s == littleend)
+#ifndef lint
+ return (char *)(big+pos);
+#else
+ return Nullch;
+#endif
+ } while (
+#ifndef lint
+ pos += screamnext[pos]
+#else
+ pos += screamnext[0]
+#endif
+ );