~ubuntu-branches/ubuntu/trusty/agrep/trusty : revision 1

1

2

#include <stdio.h>

3

#include <ctype.h>

4

#define MAXSYM 256

5

#define MAXMEMBER 8192

6

#define CHARTYPE unsigned char

7

#define MaxError 20

8

#define MAXPATT 256

9

#define MAXLINE 1024

10

#define MaxCan 2048

11

#define BLOCKSIZE 8192

12

#define MAX_SHIFT_2 4096

13

#define ON 1

14

#define LOG_ASCII 8

15

#define LOG_DNA 3

16

#define MAXMEMBER_1 65536

17

#define LONG_EXAC 20

18

#define LONG_APPX 24

19

#define W_DELIM 128

20

21

extern COUNT, FNAME, SILENT, FILENAMEONLY, num_of_matched;

22

extern DNA ; /* DNA flag is set in checksg when pattern is DNA pattern and

23

p_size > 16 */

24

extern WORDBOUND, WHOLELINE, NOUPPER;

25

extern unsigned char CurrentFileName[], Progname[];

26

extern unsigned Mask[];

27

extern unsigned endposition;

28

29

unsigned char BSize; /* log_c m */

30

unsigned char char_map[MAXSYM];

31

32

33

/* data area */

34

int shift_1;

35

CHARTYPE SHIFT[MAXSYM];

36

CHARTYPE MEMBER[MAXMEMBER];

37

CHARTYPE pat[MAXPATT];

38

unsigned Hashmask;

39

char MEMBER_1[MAXMEMBER_1];

40

CHARTYPE TR[MAXSYM];

41

42

char_tr(pat, m)

43

unsigned char *pat;

44

int *m;

45

{

46

int i;

47

unsigned char temp[MAXPATT];

48

for(i=0; i<MAXSYM; i++) TR[i] = i;

49

if(NOUPPER) {

50

for(i='A'; i<= 'Z'; i++) TR[i] = i + 'a' - 'A';

51

}

52

if(WORDBOUND) { /* SUN: To be added to be more complete */

53

for(i=0; i<128; i++) {

54

if(!isalnum(i)) TR[i] = W_DELIM;

55

}

56

}

57

if(WHOLELINE) {

58

memcpy(temp, pat, *m);

59

pat[0] = '\n';

60

memcpy(pat+1, temp, *m);

61

pat[*m+1] = '\n';

62

pat[*m+2] = 0;

63

*m = *m + 2;

64

}

65

}

66

67

sgrep(pat, m, fd, D)

68

CHARTYPE *pat; int fd, m, D;

69

{

70

CHARTYPE text[BLOCKSIZE+2*MAXLINE+MAXPATT]; /* input text stream */

71

int offset = 2*MAXLINE;

72

int buf_end, num_read, i, start, end, residue = 0;

73

if(pat[0] == '^' || pat[0] == '$') pat[0] = '\n';

74

if(pat[m-1] == '^' || pat[m-1] == '$') pat[m-1] = '\n';

75

char_tr(pat, &m); /* will change pat, and m if WHOLELINE is ON */

76

text[offset-1] = '\n'; /* initial case */

77

for(i=0; i < MAXLINE; i++) text[i] = 0; /* security zone */

78

start = offset;

79

if(WHOLELINE) start--;

80

if(m >= MAXPATT) {

81

fprintf(stderr, "%s: pattern too long\n", Progname);

82

exit(2);

83

}

84

if(D == 0) {

85

if(m > LONG_EXAC) m_preprocess(pat);

86

else prep_bm(pat, m);

87

}

88

else if (DNA) prep4(pat, m);

89

else if(m >= LONG_APPX) am_preprocess(pat);

90

else {

91

prep(pat, m, D);

92

initmask(pat, Mask, m, 0, &endposition);

93

}

94

for(i=1; i<=m; i++) text[BLOCKSIZE+offset+i] = pat[m-1];

95

/* to make sure the skip loop in bm() won't go out of bound */

96

while( (num_read = read(fd, text+offset, BLOCKSIZE)) > 0)

97

{

98

buf_end = end = offset + num_read -1 ;

99

while(text[end] != '\n' && end > offset) end--;

100

residue = buf_end - end + 1 ;

101

text[start-1] = '\n';

102

if(D==0) {

103

if(m > LONG_EXAC) monkey(pat, m, text+start, text+end);

104

else bm(pat, m, text+start, text+end);

105

}

106

else {

107

if(DNA) monkey4( pat, m, text+start, text+end, D );

108

else {

109

if(m >= LONG_APPX) a_monkey(pat, m, text+start, text+end, D);

110

else agrep(pat, m, text+start, text+end, D);

111

}

112

}

113

if(FILENAMEONLY && num_of_matched) {

114

printf("%s\n", CurrentFileName);

115

return; }

116

start = offset - residue ;

117

if(start < MAXLINE) {

118

start = MAXLINE;

119

}

120

strncpy(text+start, text+end, residue);

121

start++;

122

} /* end of while(num_read = ... */

123

return;

124

} /* end sgrep */

125

126

/* SUN: bm assumes that the content of text[n]...text[n+m-1] is

127

pat[m-1] such that the skip loop is guaranteed to terminated */

128

129

bm(pat, m, text, textend)

130

CHARTYPE *text, *textend, *pat; int m;

131

{

132

register int shift;

133

register int m1, j, d1;

134

135

/*

136

printf("%d\t", textend - text);

137

printf("%c, %c", *text, *textend);

138

*/

139

140

d1 = shift_1; /* at least 1 */

141

m1 = m - 1;

142

shift = 0;

143

while (text <= textend) {

144

shift = SHIFT[*(text += shift)];

145

while(shift) {

146

shift = SHIFT[*(text += shift)];

147

shift = SHIFT[*(text += shift)];

148

shift = SHIFT[*(text += shift)];

149

}

150

j = 0;

151

while(TR[pat[m1 - j]] == TR[*(text - j)]) {

152

if(++j == m) break; /* if statement can be

153

saved, but for safty ... */

154

}

155

if (j == m ) {

156

if(text > textend) return;

157

if(WORDBOUND) {

158

if(TR[*(text+1)] != W_DELIM) goto CONT;

159

if(TR[*(text-m)] != W_DELIM) goto CONT;

160

}

161

num_of_matched++;

162

if(FILENAMEONLY) return;

163

if(!(COUNT)) {

164

if(FNAME) printf("%s: ", CurrentFileName);

165

while(*(--text) != '\n');

166

while(*(++text) != '\n') putchar(*(text));

167

putchar(*text);

168

}

169

else { while(*text != '\n') text++; }

170

CONT:

171

shift = 1;

172

}

173

else shift = d1;

174

}

175

return;

176

}

177

178

179

/* initmask() initializes the mask table for the pattern */

180

/* endposition is a mask for the endposition of the pattern */

181

/* endposition will contain k mask bits if the pattern contains k fragments */

182

initmask(pattern, Mask, m, D, endposition)

183

CHARTYPE *pattern; unsigned *Mask; register int m, D; unsigned *endposition;

184

{

185

register unsigned Bit1, c;

186

register int i, j, frag_num;

187

188

Bit1 = 1 << 31; /* the first bit of Bit1 is 1, others 0. */

189

frag_num = D+1; *endposition = 0;

190

for (i = 0; i < frag_num; i++) *endposition = *endposition | (Bit1 >> i);

191

*endposition = *endposition >> (m - frag_num);

192

for(i = 0; i < m; i++)

193

if (pattern[i] == '^' || pattern[i] == '$') {

194

pattern[i] = '\n';

195

}

196

for(i = 0; i < MAXSYM; i++) Mask[i] = ~0;

197

for(i = 0; i < m; i++) /* initialize the mask table */

198

{ c = pattern[i];

199

for ( j = 0; j < m; j++)

200

if( c == pattern[j] )

201

Mask[c] = Mask[c] & ~( Bit1 >> j ) ;

202

}

203

}

204

205

prep(Pattern, M, D) /* preprocessing for partitioning_bm */

206

CHARTYPE *Pattern; /* can be fine-tuned to choose a better partition */

207

register int M, D;

208

{

209

register int i, j, k, p, shift;

210

register unsigned m;

211

unsigned hash, b_size = 3;

212

m = M/(D+1);

213

p = M - m*(D+1);

214

for (i = 0; i < MAXSYM; i++) SHIFT[i] = m;

215

for (i = M-1; i>=p ; i--) {

216

shift = (M-1-i)%m;

217

hash = Pattern[i];

218

if(SHIFT[hash] > shift) SHIFT[hash] = shift;

219

}

220

#ifdef DEBUG

221

for(i=0; i<M; i++) printf(" %d,", SHIFT[Pattern[i]]);

222

printf("\n");

223

#endif

224

shift_1 = m;

225

for(i=0; i<D+1; i++) {

226

j = M-1 - m*i;

227

for(k=1; k<m; k++) {

228

for(p=0; p<D+1; p++)

229

if(Pattern[j-k] == Pattern[M-1-m*p])

230

if(k < shift_1) shift_1 = k;

231

}

232

}

233

#ifdef DEBUG

234

printf("\nshift_1 = %d", shift_1);

235

#endif

236

if(shift_1 == 0) shift_1 = 1;

237

for(i=0; i<MAXMEMBER; i++) MEMBER[i] = 0;

238

if (m < 3) b_size = m;

239

for(i=0; i<D+1; i++) {

240

j = M-1 - m*i;

241

hash = 0;

242

for(k=0; k<b_size; k++) {

243

hash = (hash << 2) + Pattern[j-k];

244

}

245

#ifdef DEBUG

246

printf(" hash = %d,", hash);

247

#endif

248

MEMBER[hash] = 1;

249

}

250

}

251

252

253

agrep( pat, M, text, textend, D )

254

int M, D ; register CHARTYPE *text, *textend, *pat;

255

{

256

register int i;

257

register int m = M/(D+1);

258

register CHARTYPE *textstart;

259

register int shift, HASH;

260

int j=0, k, m1, d1;

261

int n, cdx;

262

int Candidate[MaxCan][2], round, lastend=0;

263

unsigned R1[MaxError+1], R2[MaxError+1];

264

register unsigned int r1, endpos, c;

265

unsigned currentpos;

266

unsigned Bit1;

267

unsigned r_newline;

268

269

Candidate[0][0] = Candidate[0][1] = 0;

270

d1 = shift_1;

271

cdx = 0;

272

if(m < 3) r1 = m;

273

else r1 = 3;

274

textstart = text;

275

shift = m-1;

276

while (text < textend) {

277

shift = SHIFT[*(text += shift)];

278

while(shift) {

279

shift = SHIFT[*(text += shift)];

280

shift = SHIFT[*(text += shift)];

281

}

282

j = 1; HASH = *text;

283

while(j < r1) { HASH = (HASH << 2) + *(text-j);

284

j++; }

285

if (MEMBER[HASH]) {

286

i = text - textstart;

287

if((i - M - D - 10) > Candidate[cdx][1]) {

288

Candidate[++cdx][0] = i-M-D-2;

289

Candidate[cdx][1] = i+M+D; }

290

else Candidate[cdx][1] = i+M+D;

291

shift = d1;

292

}

293

else shift = d1;

294

}

295

296

297

text = textstart;

298

n = textend - textstart;

299

r_newline = '\n';

300

/* for those candidate areas, find the D-error matches */

301

if(Candidate[1][0] < 0) Candidate[1][0] = 0;

302

endpos = endposition; /* the mask table and the endposition */

303

Bit1 = (1 << 31);

304

for(round = 0; round <= cdx; round++)

305

{ i = Candidate[round][0] ;

306

if(Candidate[round][1] > n) Candidate[round][1] = n;

307

if(i < 0) i = 0;

308

#ifdef DEBUG

309

printf("round: %d, start=%d, end=%d, ", round, i, Candidate[round][1]);

310

#endif

311

R1[0] = R2[0] = ~0;

312

R1[1] = R2[1] = ~Bit1;

313

for(k = 1; k <= D; k++) R1[k] = R2[k] = (R1[k-1] >> 1) & R1[k-1];

314

while (i < Candidate[round][1])

315

{

316

c = text[i++];

317

if(c == r_newline) {

318

for(k = 0 ; k <= D; k++) R1[k] = R2[k] = (~0 );

319

}

320

r1 = Mask[c];

321

R1[0] = (R2[0] >> 1) | r1;

322

for(k=1; k<=D; k++)

323

R1[k] = ((R2[k] >> 1) | r1) & R2[k-1] & ((R1[k-1] & R2[k-1]) >> 1);

324

if((R1[D] & endpos) == 0) {

325

num_of_matched++;

326

if(FILENAMEONLY) { return; }

327

currentpos = i;

328

if(i <= lastend) i = lastend;

329

else {

330

s_output(text, &currentpos);

331

i = currentpos;

332

}

333

lastend = i;

334

for(k=0; k<=D; k++) R1[k] = R2[k] = ~0;

335

}

336

c = text[i++];

337

if(c == r_newline) {

338

for(k = 0 ; k <= D; k++) R1[k] = R2[k] = (~0 );

339

}

340

r1 = Mask[c];

341

R2[0] = (R1[0] >> 1) | r1;

342

for(k = 1; k <= D; k++)

343

R2[k] = ((R1[k] >> 1) | r1) & R1[k-1] & ((R1[k-1] & R2[k-1]) >> 1);

344

if((R2[D] & endpos) == 0) { currentpos = i;

345

num_of_matched++;

346

if(FILENAMEONLY) { return; }

347

if(i <= lastend) i = lastend;

348

else {

349

s_output(text, &currentpos);

350

i = currentpos;

351

}

352

lastend = i;

353

for(k=0; k<=D; k++) R1[k] = R2[k] = ~0;

354

}

355

}

356

}

357

return;

358

}

359

360

s_output (text, i)

361

int *i; CHARTYPE *text;

362

{

363

int kk, bp;

364

if(SILENT) return;

365

if(COUNT) {

366

while(text[*i] != '\n') *i = *i + 1;

367

return;

368

}

369

if(FNAME == ON) printf("%s: ", CurrentFileName);

370

bp = *i;

371

while(text[--bp] != '\n');

372

while(text[++bp] != '\n') putchar(text[bp]);

373

putchar('\n');

374

*i = bp;

375

}

376

377

378

prep_bm(Pattern, m)

379

unsigned char *Pattern;

380

register m;

381

{

382

int i, j;

383

unsigned hash;

384

unsigned char lastc;

385

for (i = 0; i < MAXSYM; i++) SHIFT[i] = m;

386

for (i = m-1; i>=0; i--) {

387

hash = TR[Pattern[i]];

388

if(SHIFT[hash] >= m - 1) SHIFT[hash] = m-1-i;

389

}

390

shift_1 = m-1;

391

lastc = TR[Pattern[m-1]];

392

for (i= m-2; i>=0; i--) {

393

if(TR[Pattern[i]] == lastc )

394

{ shift_1 = m-1 - i; i = -1; }

395

}

396

if(shift_1 == 0) shift_1 = 1;

397

if(NOUPPER) for(i='A'; i<='Z'; i++) SHIFT[i] = SHIFT[i + 'a' - 'A'];

398

#ifdef DEBUG

399

for(i='a'; i<='z'; i++) printf("%c: %d", i, SHIFT[i]); printf("\n");

400

for(i='A'; i<='Z'; i++) printf("%c: %d", i, SHIFT[i]); printf("\n");

401

#endif

402

}

403

404

405

/* a_monkey() the approximate monkey move */

406

407

a_monkey( pat, m, text, textend, D )

408

register int m, D ; register CHARTYPE *text, *textend, *pat;

409

{

410

register CHARTYPE *oldtext;

411

register unsigned hash, i, hashmask, suffix_error;

412

register int m1 = m-1-D, j, pos;

413

414

hashmask = Hashmask;

415

oldtext = text;

416

while (text < textend) {

417

text = text+m1;

418

suffix_error = 0;

419

while(suffix_error <= D) {

420

hash = *text--;

421

while(MEMBER_1[hash]) {

422

hash = ((hash << LOG_ASCII) + *(text--)) & hashmask;

423

}

424

suffix_error++;

425

}

426

if(text <= oldtext) {

427

if((pos = verify(m, 2*m+D, D, pat, oldtext)) > 0) {

428

text = oldtext+pos;

429

if(text > textend) return;

430

num_of_matched++;

431

if(FILENAMEONLY) return;

432

if(!(COUNT)) {

433

if(FNAME) printf("%s: ", CurrentFileName);

434

while(*(--text) != '\n');

435

while(*(++text) != '\n') putchar(*text);

436

printf("\n");

437

}

438

else {

439

while(*text != '\n') text++;

440

}

441

}

442

else {

443

text = oldtext + m;

444

}

445

}

446

oldtext = text;

447

}

448

}

449

450

/* monkey uses two characters for delta_1 shifting */

451

452

CHARTYPE SHIFT_2[MAX_SHIFT_2];

453

454

monkey( pat, m, text, textend )

455

register int m ; register CHARTYPE *text, *textend, *pat;

456

{

457

register unsigned hash, i;

458

register CHARTYPE shift;

459

register int m1, j;

460

register unsigned r_newline;

461

462

r_newline = '\n';

463

464

m1 = m - 1;

465

text = text+m1;

466

while (text < textend) {

467

hash = *text;

468

hash = (hash << 3) + *(text-1);

469

shift = SHIFT_2[hash];

470

while(shift) {

471

text = text + shift;

472

hash = (*text << 3) + *(text-1);

473

shift = SHIFT_2[hash];

474

}

475

j = 0;

476

while(TR[pat[m1 - j]] == TR[*(text - j)]) { if(++j == m) break; }

477

if (j == m ) {

478

if(text >= textend) return;

479

num_of_matched++;

480

if(FILENAMEONLY) return;

481

if(COUNT) {

482

while (*text != r_newline) text++;

483

text--;

484

}

485

else {

486

if(FNAME) printf("%s: ", CurrentFileName);

487

while(*(--text) != r_newline);

488

while(*(++text) != r_newline) putchar(*text);

489

printf("\n");

490

text--;

491

}

492

}

493

text++;

494

}

495

}

496

497

am_preprocess(Pattern)

498

CHARTYPE *Pattern;

499

{

500

int i, j, m;

501

unsigned hash;

502

m = strlen(Pattern);

503

for (i = 1, Hashmask = 1 ; i<16 ; i++) Hashmask = (Hashmask << 1) + 1 ;

504

for (i = 0; i < MAXMEMBER_1; i++) MEMBER_1[i] = 0;

505

for (i = m-1; i>=0; i--) {

506

MEMBER_1[Pattern[i]] = 1;

507

}

508

for (i = m-1; i > 0; i--) {

509

MEMBER_1[(Pattern[i] << LOG_ASCII) + Pattern[i-1]] = 1;

510

}

511

}

512

513

514

verify(m, n, D, pat, text)

515

register int m, n, D;

516

CHARTYPE *pat, *text;

517

{

518

int A[MAXPATT], B[MAXPATT];

519

register int last = D;

520

register int cost = 0;

521

register int k, i, c;

522

register int m1 = m+1;

523

CHARTYPE *textend = text+n;

524

CHARTYPE *textbegin = text;

525

526

for (i = 0; i <= m1; i++) A[i] = B[i] = i;

527

while (text < textend)

528

{

529

for (k = 1; k <= last; k++)

530

{

531

cost = B[k-1]+1;

532

if (pat[k-1] != *text)

533

{ if (B[k]+1 < cost) cost = B[k]+1;

534

if (A[k-1]+1 < cost) cost = A[k-1]+1; }

535

else cost = cost -1;

536

A[k] = cost;

537

}

538

if(pat[last] == *text++) { A[last+1] = B[last]; last++; }

539

if(A[last] < D) A[last+1] = A[last++]+1;

540

while (A[last] > D) last = last - 1;

541

if(last >= m) return(text - textbegin - 1);

542

if(*text == '\n') {

543

last = D;

544

for(c = 0; c<=m1; c++) A[c] = B[c] = c;

545

}

546

for (k = 1; k <= last; k++)

547

{

548

cost = A[k-1]+1;

549

if (pat[k-1] != *text)

550

{ if (A[k]+1 < cost) cost = A[k]+1;

551

if (B[k-1]+1 < cost) cost = B[k-1]+1; }

552

else cost = cost -1;

553

B[k] = cost;

554

}

555

if(pat[last] == *text++) { B[last+1] = A[last]; last++; }

556

if(B[last] < D) B[last+1] = B[last++]+1;

557

while (B[last] > D) last = last -1;

558

if(last >= m) return(text - textbegin - 1);

559

if(*text == '\n') {

560

last = D;

561

for(c = 0; c<=m1; c++) A[c] = B[c] = c;

562

}

563

}

564

return(0);

565

}

566

567

/* preprocessing for monkey() */

568

569

m_preprocess(Pattern)

570

CHARTYPE *Pattern;

571

{

572

int i, j, m;

573

unsigned hash;

574

m = strlen(Pattern);

575

for (i = 0; i < MAX_SHIFT_2; i++) SHIFT_2[i] = m;

576

for (i = m-1; i>=1; i--) {

577

hash = Pattern[i];

578

hash = hash << 3;

579

for (j = 0; j< MAXSYM; j++) {

580

if(SHIFT_2[hash+j] == m) SHIFT_2[hash+j] = m-1;

581

}

582

hash = hash + Pattern[i-1];

583

if(SHIFT_2[hash] >= m - 1) SHIFT_2[hash] = m-1-i;

584

}

585

shift_1 = m-1;

586

for (i= m-2; i>=0; i--) {

587

if(Pattern[i] == Pattern[m-1] )

588

{ shift_1 = m-1 - i; i = -1; }

589

}

590

if(shift_1 == 0) shift_1 = 1;

591

SHIFT_2[0] = 0;

592

}

593

594

/* monkey4() the approximate monkey move */

595

596

char *MEMBER_D;

597

598

monkey4( pat, m, text, textend, D )

599

register int m, D ; register unsigned char *text, *pat, *textend;

600

{

601

register unsigned char *oldtext;

602

register unsigned hash, i, hashmask, suffix_error;

603

register int m1=m-1-D, j, pos;

604

605

hashmask = Hashmask;

606

oldtext = text ;

607

while (text < textend) {

608

text = text + m1;

609

suffix_error = 0;

610

while(suffix_error <= D) {

611

hash = char_map[*text--];

612

hash = ((hash << LOG_DNA) + char_map[*(text--)]) & hashmask;

613

while(MEMBER_D[hash]) {

614

hash = ((hash << LOG_DNA) + char_map[*(text--)]) & hashmask;

615

}

616

suffix_error++;

617

}

618

if(text <= oldtext) {

619

if((pos = verify(m, 2*m+D, D, pat, oldtext)) > 0) {

620

text = oldtext+pos;

621

if(text > textend) return;

622

num_of_matched++;

623

if(FILENAMEONLY) return;

624

if(!(COUNT)) {

625

if(FNAME) printf("%s:", CurrentFileName);

626

while(*(--text) != '\n');

627

while(*(++text) != '\n') putchar(*text);

628

printf("\n");

629

text++;

630

}

631

else {

632

while(*text != '\n') text++;

633

text++;

634

}

635

}

636

else text = oldtext + m;

637

}

638

oldtext = text;

639

}

640

}

641

642

prep4(Pattern, m)

643

char *Pattern; int m;

644

{

645

int i, j, k;

646

unsigned hash;

647

648

for(i=0; i< MAXSYM; i++) char_map[i] = 0;

649

char_map['a'] = char_map['A'] = 4;

650

char_map['g'] = char_map['g'] = 1;

651

char_map['t'] = char_map['t'] = 2;

652

char_map['c'] = char_map['c'] = 3;

653

char_map['n'] = char_map['n'] = 5;

654

655

BSize = blog(4, m);

656

for (i = 1, Hashmask = 1 ; i<BSize*LOG_DNA; i++) Hashmask = (Hashmask << 1) + 1 ;

657

MEMBER_D = (char *) malloc((Hashmask+1) * sizeof(char));

658

#ifdef DEBUG

659

printf("BSize = %d", BSize);

660

#endif

661

for (i=0; i <= Hashmask; i++) MEMBER_D[i] = 0;

662

for (j=0; j < BSize; j++) {

663

for(i=m-1; i >= j; i--) {

664

hash = 0;

665

for(k=0; k <= j; k++)

666

hash = (hash << LOG_DNA) +char_map[Pattern[i-k]];

667

#ifdef DEBUG

668

printf("< %d >, ", hash);

669

#endif

670

MEMBER_D[hash] = 1;

671

}

672

}

673

}

674

675

blog(base, m )

676

int base, m;

677

{

678

int i, exp;

679

exp = base;

680

m = m + m/2;

681

for (i = 1; exp < m; i++) exp = exp * base;

682

return(i);

683

}

684