• Home
  • History
  • Annotate
  • Line#
  • Navigate
  • Raw
  • Download
  • only in /netgear-WNDR4500v2-V1.0.0.60_1.0.38/ap/gpl/timemachine/gettext-0.17/gettext-tools/libgrep/
1/* kwset.c - search for any of a set of keywords.
2   Copyright 1989, 1998, 2000, 2005-2006 Free Software Foundation, Inc.
3
4   This program is free software: you can redistribute it and/or modify
5   it under the terms of the GNU General Public License as published by
6   the Free Software Foundation; either version 3 of the License, or
7   (at your option) any later version.
8
9   This program is distributed in the hope that it will be useful,
10   but WITHOUT ANY WARRANTY; without even the implied warranty of
11   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12   GNU General Public License for more details.
13
14   You should have received a copy of the GNU General Public License
15   along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
16
17/* Written August 1989 by Mike Haertel.
18   The author may be reached (Email) at the address mike@ai.mit.edu,
19   or (US mail) as Mike Haertel c/o Free Software Foundation. */
20
21/* The algorithm implemented by these routines bears a startling resemblence
22   to one discovered by Beate Commentz-Walter, although it is not identical.
23   See "A String Matching Algorithm Fast on the Average," Technical Report,
24   IBM-Germany, Scientific Center Heidelberg, Tiergartenstrasse 15, D-6900
25   Heidelberg, Germany.  See also Aho, A.V., and M. Corasick, "Efficient
26   String Matching:  An Aid to Bibliographic Search," CACM June 1975,
27   Vol. 18, No. 6, which describes the failure function used below. */
28
29#ifdef HAVE_CONFIG_H
30# include <config.h>
31#endif
32#include <sys/types.h>
33#include "kwset.h"
34#include <limits.h>
35#include <stdlib.h>
36#include "obstack.h"
37#include "gettext.h"
38#define _(str) gettext (str)
39
40#ifdef GREP
41extern char *xmalloc();
42# undef malloc
43# define malloc xmalloc
44#endif
45
46#define NCHAR (UCHAR_MAX + 1)
47#define obstack_chunk_alloc malloc
48#define obstack_chunk_free free
49
50/* Balanced tree of edges and labels leaving a given trie node. */
51struct tree
52{
53  struct tree *llink;		/* Left link; MUST be first field. */
54  struct tree *rlink;		/* Right link (to larger labels). */
55  struct trie *trie;		/* Trie node pointed to by this edge. */
56  unsigned char label;		/* Label on this edge. */
57  char balance;			/* Difference in depths of subtrees. */
58};
59
60/* Node of a trie representing a set of reversed keywords. */
61struct trie
62{
63  unsigned int accepting;	/* Word index of accepted word, or zero. */
64  struct tree *links;		/* Tree of edges leaving this node. */
65  struct trie *parent;		/* Parent of this node. */
66  struct trie *next;		/* List of all trie nodes in level order. */
67  struct trie *fail;		/* Aho-Corasick failure function. */
68  int depth;			/* Depth of this node from the root. */
69  int shift;			/* Shift function for search failures. */
70  int maxshift;			/* Max shift of self and descendents. */
71};
72
73/* Structure returned opaquely to the caller, containing everything. */
74struct kwset
75{
76  struct obstack obstack;	/* Obstack for node allocation. */
77  int words;			/* Number of words in the trie. */
78  struct trie *trie;		/* The trie itself. */
79  int mind;			/* Minimum depth of an accepting node. */
80  int maxd;			/* Maximum depth of any node. */
81  unsigned char delta[NCHAR];	/* Delta table for rapid search. */
82  struct trie *next[NCHAR];	/* Table of children of the root. */
83  char *target;			/* Target string if there's only one. */
84  int mind2;			/* Used in Boyer-Moore search for one string. */
85  char const *trans;		/* Character translation table. */
86};
87
88/* Allocate and initialize a keyword set object, returning an opaque
89   pointer to it.  Return NULL if memory is not available. */
90kwset_t
91kwsalloc (char const *trans)
92{
93  struct kwset *kwset;
94
95  kwset = (struct kwset *) malloc(sizeof (struct kwset));
96  if (!kwset)
97    return 0;
98
99  obstack_init(&kwset->obstack);
100  kwset->words = 0;
101  kwset->trie
102    = (struct trie *) obstack_alloc(&kwset->obstack, sizeof (struct trie));
103  if (!kwset->trie)
104    {
105      kwsfree((kwset_t) kwset);
106      return 0;
107    }
108  kwset->trie->accepting = 0;
109  kwset->trie->links = 0;
110  kwset->trie->parent = 0;
111  kwset->trie->next = 0;
112  kwset->trie->fail = 0;
113  kwset->trie->depth = 0;
114  kwset->trie->shift = 0;
115  kwset->mind = INT_MAX;
116  kwset->maxd = -1;
117  kwset->target = 0;
118  kwset->trans = trans;
119
120  return (kwset_t) kwset;
121}
122
123/* Add the given string to the contents of the keyword set.  Return NULL
124   for success, an error message otherwise. */
125const char *
126kwsincr (kwset_t kws, char const *text, size_t len)
127{
128  struct kwset *kwset;
129  register struct trie *trie;
130  register unsigned char label;
131  register struct tree *link;
132  register int depth;
133  struct tree *links[12];
134  enum { L, R } dirs[12];
135  struct tree *t, *r, *l, *rl, *lr;
136
137  kwset = (struct kwset *) kws;
138  trie = kwset->trie;
139  text += len;
140
141  /* Descend the trie (built of reversed keywords) character-by-character,
142     installing new nodes when necessary. */
143  while (len--)
144    {
145      label = kwset->trans ? kwset->trans[(unsigned char) *--text] : *--text;
146
147      /* Descend the tree of outgoing links for this trie node,
148	 looking for the current character and keeping track
149	 of the path followed. */
150      link = trie->links;
151      links[0] = (struct tree *) &trie->links;
152      dirs[0] = L;
153      depth = 1;
154
155      while (link && label != link->label)
156	{
157	  links[depth] = link;
158	  if (label < link->label)
159	    dirs[depth++] = L, link = link->llink;
160	  else
161	    dirs[depth++] = R, link = link->rlink;
162	}
163
164      /* The current character doesn't have an outgoing link at
165	 this trie node, so build a new trie node and install
166	 a link in the current trie node's tree. */
167      if (!link)
168	{
169	  link = (struct tree *) obstack_alloc(&kwset->obstack,
170					       sizeof (struct tree));
171	  if (!link)
172	    return _("memory exhausted");
173	  link->llink = 0;
174	  link->rlink = 0;
175	  link->trie = (struct trie *) obstack_alloc(&kwset->obstack,
176						     sizeof (struct trie));
177	  if (!link->trie)
178	    return _("memory exhausted");
179	  link->trie->accepting = 0;
180	  link->trie->links = 0;
181	  link->trie->parent = trie;
182	  link->trie->next = 0;
183	  link->trie->fail = 0;
184	  link->trie->depth = trie->depth + 1;
185	  link->trie->shift = 0;
186	  link->label = label;
187	  link->balance = 0;
188
189	  /* Install the new tree node in its parent. */
190	  if (dirs[--depth] == L)
191	    links[depth]->llink = link;
192	  else
193	    links[depth]->rlink = link;
194
195	  /* Back up the tree fixing the balance flags. */
196	  while (depth && !links[depth]->balance)
197	    {
198	      if (dirs[depth] == L)
199		--links[depth]->balance;
200	      else
201		++links[depth]->balance;
202	      --depth;
203	    }
204
205	  /* Rebalance the tree by pointer rotations if necessary. */
206	  if (depth && ((dirs[depth] == L && --links[depth]->balance)
207			|| (dirs[depth] == R && ++links[depth]->balance)))
208	    {
209	      switch (links[depth]->balance)
210		{
211		case (char) -2:
212		  switch (dirs[depth + 1])
213		    {
214		    case L:
215		      r = links[depth], t = r->llink, rl = t->rlink;
216		      t->rlink = r, r->llink = rl;
217		      t->balance = r->balance = 0;
218		      break;
219		    case R:
220		      r = links[depth], l = r->llink, t = l->rlink;
221		      rl = t->rlink, lr = t->llink;
222		      t->llink = l, l->rlink = lr, t->rlink = r, r->llink = rl;
223		      l->balance = t->balance != 1 ? 0 : -1;
224		      r->balance = t->balance != (char) -1 ? 0 : 1;
225		      t->balance = 0;
226		      break;
227		    default:
228		      abort ();
229		    }
230		  break;
231		case 2:
232		  switch (dirs[depth + 1])
233		    {
234		    case R:
235		      l = links[depth], t = l->rlink, lr = t->llink;
236		      t->llink = l, l->rlink = lr;
237		      t->balance = l->balance = 0;
238		      break;
239		    case L:
240		      l = links[depth], r = l->rlink, t = r->llink;
241		      lr = t->llink, rl = t->rlink;
242		      t->llink = l, l->rlink = lr, t->rlink = r, r->llink = rl;
243		      l->balance = t->balance != 1 ? 0 : -1;
244		      r->balance = t->balance != (char) -1 ? 0 : 1;
245		      t->balance = 0;
246		      break;
247		    default:
248		      abort ();
249		    }
250		  break;
251		default:
252		  abort ();
253		}
254
255	      if (dirs[depth - 1] == L)
256		links[depth - 1]->llink = t;
257	      else
258		links[depth - 1]->rlink = t;
259	    }
260	}
261
262      trie = link->trie;
263    }
264
265  /* Mark the node we finally reached as accepting, encoding the
266     index number of this word in the keyword set so far. */
267  if (!trie->accepting)
268    trie->accepting = 1 + 2 * kwset->words;
269  ++kwset->words;
270
271  /* Keep track of the longest and shortest string of the keyword set. */
272  if (trie->depth < kwset->mind)
273    kwset->mind = trie->depth;
274  if (trie->depth > kwset->maxd)
275    kwset->maxd = trie->depth;
276
277  return 0;
278}
279
280/* Enqueue the trie nodes referenced from the given tree in the
281   given queue. */
282static void
283enqueue (struct tree *tree, struct trie **last)
284{
285  if (!tree)
286    return;
287  enqueue(tree->llink, last);
288  enqueue(tree->rlink, last);
289  (*last) = (*last)->next = tree->trie;
290}
291
292/* Compute the Aho-Corasick failure function for the trie nodes referenced
293   from the given tree, given the failure function for their parent as
294   well as a last resort failure node. */
295static void
296treefails (register struct tree const *tree, struct trie const *fail,
297	   struct trie *recourse)
298{
299  register struct tree *link;
300
301  if (!tree)
302    return;
303
304  treefails(tree->llink, fail, recourse);
305  treefails(tree->rlink, fail, recourse);
306
307  /* Find, in the chain of fails going back to the root, the first
308     node that has a descendent on the current label. */
309  while (fail)
310    {
311      link = fail->links;
312      while (link && tree->label != link->label)
313	if (tree->label < link->label)
314	  link = link->llink;
315	else
316	  link = link->rlink;
317      if (link)
318	{
319	  tree->trie->fail = link->trie;
320	  return;
321	}
322      fail = fail->fail;
323    }
324
325  tree->trie->fail = recourse;
326}
327
328/* Set delta entries for the links of the given tree such that
329   the preexisting delta value is larger than the current depth. */
330static void
331treedelta (register struct tree const *tree,
332	   register unsigned int depth,
333	   unsigned char delta[])
334{
335  if (!tree)
336    return;
337  treedelta(tree->llink, depth, delta);
338  treedelta(tree->rlink, depth, delta);
339  if (depth < delta[tree->label])
340    delta[tree->label] = depth;
341}
342
343/* Return true if A has every label in B. */
344static int
345hasevery (register struct tree const *a, register struct tree const *b)
346{
347  if (!b)
348    return 1;
349  if (!hasevery(a, b->llink))
350    return 0;
351  if (!hasevery(a, b->rlink))
352    return 0;
353  while (a && b->label != a->label)
354    if (b->label < a->label)
355      a = a->llink;
356    else
357      a = a->rlink;
358  return !!a;
359}
360
361/* Compute a vector, indexed by character code, of the trie nodes
362   referenced from the given tree. */
363static void
364treenext (struct tree const *tree, struct trie *next[])
365{
366  if (!tree)
367    return;
368  treenext(tree->llink, next);
369  treenext(tree->rlink, next);
370  next[tree->label] = tree->trie;
371}
372
373/* Compute the shift for each trie node, as well as the delta
374   table and next cache for the given keyword set. */
375const char *
376kwsprep (kwset_t kws)
377{
378  register struct kwset *kwset;
379  register int i;
380  register struct trie *curr, *fail;
381  register char const *trans;
382  unsigned char delta[NCHAR];
383  struct trie *last, *next[NCHAR];
384
385  kwset = (struct kwset *) kws;
386
387  /* Initial values for the delta table; will be changed later.  The
388     delta entry for a given character is the smallest depth of any
389     node at which an outgoing edge is labeled by that character. */
390  if (kwset->mind < 256)
391    for (i = 0; i < NCHAR; ++i)
392      delta[i] = kwset->mind;
393  else
394    for (i = 0; i < NCHAR; ++i)
395      delta[i] = 255;
396
397  /* Check if we can use the simple boyer-moore algorithm, instead
398     of the hairy commentz-walter algorithm. */
399  if (kwset->words == 1 && kwset->trans == 0)
400    {
401      /* Looking for just one string.  Extract it from the trie. */
402      kwset->target = (char *) obstack_alloc(&kwset->obstack, kwset->mind);
403      for (i = kwset->mind - 1, curr = kwset->trie; i >= 0; --i)
404	{
405	  kwset->target[i] = curr->links->label;
406	  curr = curr->links->trie;
407	}
408      /* Build the Boyer Moore delta.  Boy that's easy compared to CW. */
409      for (i = 0; i < kwset->mind; ++i)
410	delta[(unsigned char) kwset->target[i]] = kwset->mind - (i + 1);
411      kwset->mind2 = kwset->mind;
412      /* Find the minimal delta2 shift that we might make after
413	 a backwards match has failed. */
414      for (i = 0; i < kwset->mind - 1; ++i)
415	if (kwset->target[i] == kwset->target[kwset->mind - 1])
416	  kwset->mind2 = kwset->mind - (i + 1);
417    }
418  else
419    {
420      /* Traverse the nodes of the trie in level order, simultaneously
421	 computing the delta table, failure function, and shift function. */
422      for (curr = last = kwset->trie; curr; curr = curr->next)
423	{
424	  /* Enqueue the immediate descendents in the level order queue. */
425	  enqueue(curr->links, &last);
426
427	  curr->shift = kwset->mind;
428	  curr->maxshift = kwset->mind;
429
430	  /* Update the delta table for the descendents of this node. */
431	  treedelta(curr->links, curr->depth, delta);
432
433	  /* Compute the failure function for the decendents of this node. */
434	  treefails(curr->links, curr->fail, kwset->trie);
435
436	  /* Update the shifts at each node in the current node's chain
437	     of fails back to the root. */
438	  for (fail = curr->fail; fail; fail = fail->fail)
439	    {
440	      /* If the current node has some outgoing edge that the fail
441		 doesn't, then the shift at the fail should be no larger
442		 than the difference of their depths. */
443	      if (!hasevery(fail->links, curr->links))
444		if (curr->depth - fail->depth < fail->shift)
445		  fail->shift = curr->depth - fail->depth;
446
447	      /* If the current node is accepting then the shift at the
448		 fail and its descendents should be no larger than the
449		 difference of their depths. */
450	      if (curr->accepting && fail->maxshift > curr->depth - fail->depth)
451		fail->maxshift = curr->depth - fail->depth;
452	    }
453	}
454
455      /* Traverse the trie in level order again, fixing up all nodes whose
456	 shift exceeds their inherited maxshift. */
457      for (curr = kwset->trie->next; curr; curr = curr->next)
458	{
459	  if (curr->maxshift > curr->parent->maxshift)
460	    curr->maxshift = curr->parent->maxshift;
461	  if (curr->shift > curr->maxshift)
462	    curr->shift = curr->maxshift;
463	}
464
465      /* Create a vector, indexed by character code, of the outgoing links
466	 from the root node. */
467      for (i = 0; i < NCHAR; ++i)
468	next[i] = 0;
469      treenext(kwset->trie->links, next);
470
471      if ((trans = kwset->trans) != 0)
472	for (i = 0; i < NCHAR; ++i)
473	  kwset->next[i] = next[(unsigned char) trans[i]];
474      else
475	for (i = 0; i < NCHAR; ++i)
476	  kwset->next[i] = next[i];
477    }
478
479  /* Fix things up for any translation table. */
480  if ((trans = kwset->trans) != 0)
481    for (i = 0; i < NCHAR; ++i)
482      kwset->delta[i] = delta[(unsigned char) trans[i]];
483  else
484    for (i = 0; i < NCHAR; ++i)
485      kwset->delta[i] = delta[i];
486
487  return 0;
488}
489
490#define U(C) ((unsigned char) (C))
491
492/* Fast boyer-moore search. */
493static size_t
494bmexec (kwset_t kws, char const *text, size_t size)
495{
496  struct kwset const *kwset;
497  register unsigned char const *d1;
498  register char const *ep, *sp, *tp;
499  register int d, gc, i, len, md2;
500
501  kwset = (struct kwset const *) kws;
502  len = kwset->mind;
503
504  if (len == 0)
505    return 0;
506  if (len > size)
507    return -1;
508  if (len == 1)
509    {
510      tp = (const char *) memchr (text, kwset->target[0], size);
511      return tp ? tp - text : -1;
512    }
513
514  d1 = kwset->delta;
515  sp = kwset->target + len;
516  gc = U(sp[-2]);
517  md2 = kwset->mind2;
518  tp = text + len;
519
520  /* Significance of 12: 1 (initial offset) + 10 (skip loop) + 1 (md2). */
521  if (size > 12 * len)
522    /* 11 is not a bug, the initial offset happens only once. */
523    for (ep = text + size - 11 * len;;)
524      {
525	while (tp <= ep)
526	  {
527	    d = d1[U(tp[-1])], tp += d;
528	    d = d1[U(tp[-1])], tp += d;
529	    if (d == 0)
530	      goto found;
531	    d = d1[U(tp[-1])], tp += d;
532	    d = d1[U(tp[-1])], tp += d;
533	    d = d1[U(tp[-1])], tp += d;
534	    if (d == 0)
535	      goto found;
536	    d = d1[U(tp[-1])], tp += d;
537	    d = d1[U(tp[-1])], tp += d;
538	    d = d1[U(tp[-1])], tp += d;
539	    if (d == 0)
540	      goto found;
541	    d = d1[U(tp[-1])], tp += d;
542	    d = d1[U(tp[-1])], tp += d;
543	  }
544	break;
545      found:
546	if (U(tp[-2]) == gc)
547	  {
548	    for (i = 3; i <= len && U(tp[-i]) == U(sp[-i]); ++i)
549	      ;
550	    if (i > len)
551	      return tp - len - text;
552	  }
553	tp += md2;
554      }
555
556  /* Now we have only a few characters left to search.  We
557     carefully avoid ever producing an out-of-bounds pointer. */
558  ep = text + size;
559  d = d1[U(tp[-1])];
560  while (d <= ep - tp)
561    {
562      d = d1[U((tp += d)[-1])];
563      if (d != 0)
564	continue;
565      if (U(tp[-2]) == gc)
566	{
567	  for (i = 3; i <= len && U(tp[-i]) == U(sp[-i]); ++i)
568	    ;
569	  if (i > len)
570	    return tp - len - text;
571	}
572      d = md2;
573    }
574
575  return -1;
576}
577
578/* Hairy multiple string search. */
579static size_t
580cwexec (kwset_t kws, char const *text, size_t len, struct kwsmatch *kwsmatch)
581{
582  struct kwset const *kwset;
583  struct trie * const *next;
584  struct trie const *trie;
585  struct trie const *accept;
586  char const *beg, *lim, *mch, *lmch;
587  register unsigned char c;
588  register unsigned char const *delta;
589  register int d;
590  register char const *end, *qlim;
591  register struct tree const *tree;
592  register char const *trans;
593
594  accept = NULL;
595
596  /* Initialize register copies and look for easy ways out. */
597  kwset = (struct kwset *) kws;
598  if (len < kwset->mind)
599    return -1;
600  next = kwset->next;
601  delta = kwset->delta;
602  trans = kwset->trans;
603  lim = text + len;
604  end = text;
605  if ((d = kwset->mind) != 0)
606    mch = 0;
607  else
608    {
609      mch = text, accept = kwset->trie;
610      goto match;
611    }
612
613  if (len >= 4 * kwset->mind)
614    qlim = lim - 4 * kwset->mind;
615  else
616    qlim = 0;
617
618  while (lim - end >= d)
619    {
620      if (qlim && end <= qlim)
621	{
622	  end += d - 1;
623	  while ((d = delta[c = *end]) && end < qlim)
624	    {
625	      end += d;
626	      end += delta[(unsigned char) *end];
627	      end += delta[(unsigned char) *end];
628	    }
629	  ++end;
630	}
631      else
632	d = delta[c = (end += d)[-1]];
633      if (d)
634	continue;
635      beg = end - 1;
636      trie = next[c];
637      if (trie->accepting)
638	{
639	  mch = beg;
640	  accept = trie;
641	}
642      d = trie->shift;
643      while (beg > text)
644	{
645	  c = trans ? trans[(unsigned char) *--beg] : *--beg;
646	  tree = trie->links;
647	  while (tree && c != tree->label)
648	    if (c < tree->label)
649	      tree = tree->llink;
650	    else
651	      tree = tree->rlink;
652	  if (tree)
653	    {
654	      trie = tree->trie;
655	      if (trie->accepting)
656		{
657		  mch = beg;
658		  accept = trie;
659		}
660	    }
661	  else
662	    break;
663	  d = trie->shift;
664	}
665      if (mch)
666	goto match;
667    }
668  return -1;
669
670 match:
671  /* Given a known match, find the longest possible match anchored
672     at or before its starting point.  This is nearly a verbatim
673     copy of the preceding main search loops. */
674  if (lim - mch > kwset->maxd)
675    lim = mch + kwset->maxd;
676  lmch = 0;
677  d = 1;
678  while (lim - end >= d)
679    {
680      if ((d = delta[c = (end += d)[-1]]) != 0)
681	continue;
682      beg = end - 1;
683      if (!(trie = next[c]))
684	{
685	  d = 1;
686	  continue;
687	}
688      if (trie->accepting && beg <= mch)
689	{
690	  lmch = beg;
691	  accept = trie;
692	}
693      d = trie->shift;
694      while (beg > text)
695	{
696	  c = trans ? trans[(unsigned char) *--beg] : *--beg;
697	  tree = trie->links;
698	  while (tree && c != tree->label)
699	    if (c < tree->label)
700	      tree = tree->llink;
701	    else
702	      tree = tree->rlink;
703	  if (tree)
704	    {
705	      trie = tree->trie;
706	      if (trie->accepting && beg <= mch)
707		{
708		  lmch = beg;
709		  accept = trie;
710		}
711	    }
712	  else
713	    break;
714	  d = trie->shift;
715	}
716      if (lmch)
717	{
718	  mch = lmch;
719	  goto match;
720	}
721      if (!d)
722	d = 1;
723    }
724
725  if (kwsmatch)
726    {
727      kwsmatch->index = accept->accepting / 2;
728      kwsmatch->offset[0] = mch - text;
729      kwsmatch->size[0] = accept->depth;
730    }
731  return mch - text;
732}
733
734/* Search through the given text for a match of any member of the
735   given keyword set.  Return a pointer to the first character of
736   the matching substring, or NULL if no match is found.  If FOUNDLEN
737   is non-NULL store in the referenced location the length of the
738   matching substring.  Similarly, if FOUNDIDX is non-NULL, store
739   in the referenced location the index number of the particular
740   keyword matched. */
741size_t
742kwsexec (kwset_t kws, char const *text, size_t size,
743	 struct kwsmatch *kwsmatch)
744{
745  struct kwset const *kwset = (struct kwset *) kws;
746  if (kwset->words == 1 && kwset->trans == 0)
747    {
748      size_t ret = bmexec (kws, text, size);
749      if (kwsmatch != 0 && ret != (size_t) -1)
750	{
751	  kwsmatch->index = 0;
752	  kwsmatch->offset[0] = ret;
753	  kwsmatch->size[0] = kwset->mind;
754	}
755      return ret;
756    }
757  else
758    return cwexec(kws, text, size, kwsmatch);
759}
760
761/* Free the components of the given keyword set. */
762void
763kwsfree (kwset_t kws)
764{
765  struct kwset *kwset;
766
767  kwset = (struct kwset *) kws;
768  obstack_free(&kwset->obstack, 0);
769  free(kws);
770}
771