1 /**
2 * @namespace biewlib
3 * @file biewlib/biewlib.c
4 * @brief This file contains implementation of extension of C library.
5 * @version -
6 * @remark this source file is part of Binary vIEW project (BIEW).
7 * The Binary vIEW (BIEW) is copyright (C) 1995 Nickols_K.
8 * All rights reserved. This software is redistributable under the
9 * licence given in the file "Licence.en" ("Licence.ru" in russian
10 * translation) distributed in the BIEW archive.
11 * @note Requires POSIX compatible development system
12 *
13 * @author Nickols_K
14 * @since 1995
15 * @note Development, fixes and improvements
16 * @todo Increase number of functions
17 **/
18 #include <string.h>
19 #include <stdlib.h>
20 #include <stdarg.h>
21 #include <stdio.h>
22 #include <ctype.h>
23 #include <limits.h>
24 #include "biewlib/sysdep/__config.h"
25 #if __WORDSIZE == 16
26 #include <mem.h>
27 #endif
28 #include "biewlib/pmalloc.h"
29
isseparate(int ch)30 tBool __FASTCALL__ isseparate(int ch) { return (isspace(ch) || ispunct(ch)); }
31
__nls_PrepareOEMForTVio(tvioBuff * it,unsigned size)32 void __FASTCALL__ __nls_PrepareOEMForTVio(tvioBuff *it,unsigned size)
33 {
34 unsigned i;
35 unsigned char ch;
36 for(i = 0;i < size;i++)
37 {
38 ch = it->chars[i];
39 it->oem_pg[i] = NLS_IS_OEMPG(ch) ? ch : 0;
40 }
41 __nls_OemToOsdep(it->chars,size);
42 }
43
memupr(void * ptr,unsigned n)44 void __FASTCALL__ memupr(void *ptr,unsigned n)
45 {
46 unsigned i;
47 for(i = 0;i < n;i++)
48 ((char *)ptr)[i] = toupper(((char *)ptr)[i]);
49 }
50
memlwr(void * ptr,unsigned n)51 void __FASTCALL__ memlwr(void *ptr,unsigned n)
52 {
53 unsigned i;
54 for(i = 0;i < n;i++)
55 ((char *)ptr)[i] = tolower(((char *)ptr)[i]);
56 }
57
szTrimTrailingSpace(char * str)58 int __FASTCALL__ szTrimTrailingSpace(char *str)
59 {
60 unsigned len;
61 int ret;
62 len = strlen(str);
63 ret = 0;
64 while(len)
65 {
66 unsigned char ch;
67 ch = str[len-1];
68 if(isspace(ch) && ch < 0x80) { str[--len] = '\0'; ret++; }
69 else break;
70 }
71 return ret;
72 }
73
szTrimLeadingSpace(char * str)74 int __FASTCALL__ szTrimLeadingSpace(char *str)
75 {
76 unsigned i,freq,len;
77 len = strlen(str);
78 for(i = freq = 0;i < len;i++)
79 {
80 unsigned char ch;
81 ch = str[i];
82 if(isspace(ch) && ch < 0x80) freq++;
83 else break;
84 }
85 if(freq)
86 {
87 len -= freq;
88 memmove(str,&str[freq],len+1);
89 }
90 return freq;
91 }
92
93 #define TEXT_TAB 8
94
szSpace2Tab(char * dest,const char * src)95 void __FASTCALL__ szSpace2Tab(char *dest,const char * src)
96 {
97 unsigned int i,len,limit,dest_idx;
98 int j;
99 unsigned char buff[8],nspc;
100 len = strlen(src);
101 i = 0;
102 dest_idx = 0;
103 while(1)
104 {
105 if(i + TEXT_TAB < len)
106 {
107 memcpy(buff,&src[i],8);
108 i+=8;
109 /* scan */
110 nspc = 0;
111 for(j = TEXT_TAB-1;j >= 0;j--)
112 {
113 if(buff[j] != ' ') break;
114 else nspc++;
115 }
116 limit = TEXT_TAB - nspc;
117 memcpy(&dest[dest_idx],buff,limit);
118 dest_idx += limit;
119 if(nspc) dest[dest_idx++] = '\t';
120 }
121 else
122 {
123 limit = len - i;
124 memcpy(&dest[dest_idx],&src[i],limit);
125 dest_idx += limit;
126 i += limit;
127 break;
128 }
129 }
130 dest[dest_idx] = '\0';
131 }
132
szTab2Space(char * dest,const char * src)133 int __FASTCALL__ szTab2Space(char * dest,const char * src)
134 {
135 int i,k,len;
136 size_t size;
137 unsigned int freq;
138 unsigned char ch;
139 len = strlen(src);
140 for(freq = 0,i = k = 0;i < len;i++,freq++)
141 {
142 ch = src[i];
143 if(ch == '\t')
144 {
145 size = TEXT_TAB - (freq%TEXT_TAB);
146 memset(&dest[k],' ',size);
147 k += size;
148 freq += size-1;
149 }
150 else
151 {
152 dest[k] = ch;
153 k++;
154 }
155 }
156 return k;
157 }
158
szKillSpaceAround(char * str,char * place)159 char * __FASTCALL__ szKillSpaceAround(char *str,char *place)
160 {
161 char *sptr;
162 unsigned nmoves,len,idx,freq;
163 unsigned char prev;
164 unsigned char ch;
165 prev = *place;
166 len = strlen(str);
167 *place = 0;
168 idx = place - str;
169 nmoves = szTrimTrailingSpace(str);
170 sptr = place;
171 freq = 0;
172 sptr++;
173 while((ch = *sptr) != 0)
174 {
175 if(isspace(ch)) freq++;
176 else break;
177 sptr++;
178 }
179 memmove(&str[idx-nmoves],&str[idx+freq],len-idx+1-freq);
180 str[idx-nmoves] = prev;
181 return &str[idx-nmoves];
182 }
183
184
185 #if __WORDSIZE == 16
HMemCpy(void huge * _dest,const void huge * _source,unsigned long n)186 void huge * __FASTCALL__ HMemCpy(void huge *_dest, const void huge *_source, unsigned long n)
187 {
188 long i;
189 for(i = 0;i < n;i++)
190 {
191 ((char huge *)_dest)[i] = ((const char huge *)_source)[i];
192 }
193 return _dest;
194 }
195 #endif
196
197 #ifdef __GNUC__
198 /* (emx+gcc) -- Copyright (c) 1990-1995 by Eberhard Mattes */
ltoa(long value,char * string,int radix)199 char *ltoa (long value, char *string, int radix)
200 {
201 char *dst;
202
203 dst = string;
204 if (radix < 2 || radix > 36) *dst = 0;
205 else
206 {
207 unsigned long x;
208 int i, n;
209 char digits[32];
210 if (radix == 10 && value < 0)
211 {
212 *dst++ = '-';
213 x = -value;
214 }
215 else x = value;
216 i = 0;
217 do
218 {
219 n = x % radix;
220 digits[i++] = n+(n < 10 ? '0' : 'A'-10);
221 x /= radix;
222 } while (x != 0);
223 while (i > 0) *dst++ = digits[--i];
224 *dst = 0;
225 }
226 return string;
227 }
228
ultoa(unsigned long value,char * string,int radix)229 char *ultoa (unsigned long value, char *string, int radix)
230 {
231 char *dst;
232
233 dst = string;
234 if (radix < 2 || radix > 36) *dst = 0;
235 else
236 {
237 int i;
238 unsigned n;
239 char digits[32];
240 i = 0;
241 do
242 {
243 n = value % radix;
244 digits[i++] = n+(n < 10 ? '0' : 'A'-10);
245 value /= radix;
246 } while (value != 0);
247 while (i > 0) *dst++ = digits[--i];
248 *dst = 0;
249 }
250 return string;
251 }
252 #endif
253
254 #if __WORDSIZE >= 32
lltoa(long long int value,char * string,int radix)255 char *lltoa (long long int value, char *string, int radix)
256 {
257 char *dst;
258
259 dst = string;
260 if (radix < 2 || radix > 36) *dst = 0;
261 else
262 {
263 unsigned long long int x;
264 int i, n;
265 char digits[64];
266 if (radix == 10 && value < 0)
267 {
268 *dst++ = '-';
269 x = -value;
270 }
271 else x = value;
272 i = 0;
273 do
274 {
275 n = x % radix;
276 digits[i++] = n+(n < 10 ? '0' : 'A'-10);
277 x /= radix;
278 } while (x != 0);
279 while (i > 0) *dst++ = digits[--i];
280 *dst = 0;
281 }
282 return string;
283 }
284
ulltoa(unsigned long long int value,char * string,int radix)285 char *ulltoa (unsigned long long int value, char *string, int radix)
286 {
287 char *dst;
288
289 dst = string;
290 if (radix < 2 || radix > 36) *dst = 0;
291 else
292 {
293 int i;
294 unsigned n;
295 char digits[64];
296 i = 0;
297 do
298 {
299 n = value % radix;
300 digits[i++] = n+(n < 10 ? '0' : 'A'-10);
301 value /= radix;
302 } while (value != 0);
303 while (i > 0) *dst++ = digits[--i];
304 *dst = 0;
305 }
306 return string;
307 }
308 #endif
309
310 /*
311 Using own code for qsort and bsearch functions is guarantee of stable work */
312
313 /* Copyright (C) 1994 DJ Delorie, see COPYING.DJ for details */
314 /* Modified for use with 16-bits huge arrays by Nickols_K */
315 /*-
316 * Copyright (c) 1980, 1983 The Regents of the University of California.
317 * All rights reserved.
318 *
319 * Redistribution and use in source and binary forms are permitted
320 * provided that: (1) source distributions retain this entire copyright
321 * notice and comment, and (2) distributions including binaries display
322 * the following acknowledgement: ``This product includes software
323 * developed by the University of California, Berkeley and its contributors''
324 * in the documentation or other materials provided with the distribution
325 * and in all advertising materials mentioning features or use of this
326 * software. Neither the name of the University nor the names of its
327 * contributors may be used to endorse or promote products derived
328 * from this software without specific prior written permission.
329 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
330 * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
331 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
332 */
333
334 /*
335 * qsort.c:
336 * Our own version of the system qsort routine which is faster by an average
337 * of 25%, with lows and highs of 10% and 50%.
338 * The THRESHold below is the insertion sort threshold, and has been adjusted
339 * for records of size 48 bytes.
340 * The MTHREShold is where we stop finding a better median.
341 */
342
343 #define THRESH 4 /**< threshold for insertion */
344 #define MTHRESH 6 /**< threshold for median */
345
346 static func_compare qcmp; /**< the comparison routine */
347 static int qsz; /**< size of each record */
348 static long thresh; /**< THRESHold in chars */
349 static long mthresh; /**< MTHRESHold in chars */
350
351 /**
352 * qst:
353 * Do a quicksort
354 * First, find the median element, and put that one in the first place as the
355 * discriminator. (This "median" is just the median of the first, last and
356 * middle elements). (Using this median instead of the first element is a big
357 * win). Then, the usual partitioning/swapping, followed by moving the
358 * discriminator into the right place. Then, figure out the sizes of the two
359 * partions, do the smaller one recursively and the larger one via a repeat of
360 * this code. Stopping when there are less than THRESH elements in a partition
361 * and cleaning up with an insertion sort (in our caller) is a huge win.
362 * All data swaps are done in-line, which is space-losing but time-saving.
363 * (And there are only three places where this is done).
364 */
qst(char __HUGE__ * base,char __HUGE__ * max)365 static void __NEAR__ qst(char __HUGE__ *base, char __HUGE__ *max)
366 {
367 long ii,lo,hi;
368 char __HUGE__ *i, __HUGE__ *j,__HUGE__ *jj;
369 char __HUGE__ *mid, __HUGE__ *tmp;
370
371 /*
372 * At the top here, lo is the number of characters of elements in the
373 * current partition. (Which should be max - base).
374 * Find the median of the first, last, and middle element and make
375 * that the middle element. Set j to largest of first and middle.
376 * If max is larger than that guy, then it's that guy, else compare
377 * max with loser of first and take larger. Things are set up to
378 * prefer the middle, then the first in case of ties.
379 */
380 lo = max - base; /* number of elements as chars */
381 do {
382 mid = i = base + qsz * ((lo / qsz) >> 1);
383 if (lo >= mthresh)
384 {
385 j = (qcmp((jj = base), i) > 0 ? jj : i);
386 if (qcmp(j, (tmp = max - qsz)) > 0)
387 {
388 /* switch to first loser */
389 j = (j == jj ? i : jj);
390 if (qcmp(j, tmp) < 0)
391 j = tmp;
392 }
393 if (j != i)
394 {
395 ii = qsz;
396 do{
397 __XchgB__(i,j);
398 i++; j++;
399 } while (--ii);
400 }
401 }
402 /*
403 * Semi-standard quicksort partitioning/swapping
404 */
405 for (i = base, j = max - qsz; ; )
406 {
407 while (i < mid && qcmp(i, mid) <= 0)
408 i += qsz;
409 while (j > mid)
410 {
411 if (qcmp(mid, j) <= 0)
412 {
413 j -= qsz;
414 continue;
415 }
416 tmp = i + qsz; /* value of i after swap */
417 if (i == mid)
418 {
419 /* j <-> mid, new mid is j */
420 mid = jj = j;
421 }
422 else
423 {
424 /* i <-> j */
425 jj = j;
426 j -= qsz;
427 }
428 goto swap;
429 }
430 if (i == mid)
431 {
432 break;
433 }
434 else
435 {
436 /* i <-> mid, new mid is i */
437 jj = mid;
438 tmp = mid = i; /* value of i after swap */
439 j -= qsz;
440 }
441 swap:
442 ii = qsz;
443 do{
444 __XchgB__(i,jj);
445 i++; jj++;
446 } while (--ii);
447 i = tmp;
448 }
449 /*
450 * Look at sizes of the two partitions, do the smaller
451 * one first by recursion, then do the larger one by
452 * making sure lo is its size, base and max are update
453 * correctly, and branching back. But only repeat
454 * (recursively or by branching) if the partition is
455 * of at least size THRESH.
456 */
457 i = (j = mid) + qsz;
458 if ((lo = j - base) <= (hi = max - i))
459 {
460 if (lo >= thresh)
461 qst(base, j);
462 base = i;
463 lo = hi;
464 }
465 else
466 {
467 if (hi >= thresh)
468 qst(i, max);
469 max = j;
470 }
471 } while (lo >= thresh);
472 }
473
474 /*
475 * qsort:
476 * First, set up some global parameters for qst to share. Then, quicksort
477 * with qst(), and then a cleanup insertion sort ourselves. Sound simple?
478 * It's not...
479 */
HQSort(void __HUGE__ * base0,unsigned long num,unsigned width,func_compare compare)480 void __FASTCALL__ HQSort(void __HUGE__ *base0,unsigned long num, unsigned width,
481 func_compare compare)
482 {
483 char __HUGE__ *base = (char __HUGE__ *)base0;
484 char __HUGE__ *i, __HUGE__ *j, __HUGE__ *lo, __HUGE__ *hi;
485 char __HUGE__ *min, __HUGE__ *max;
486 register char c;
487
488 if (num <= 1)
489 return;
490 qsz = width;
491 qcmp = compare;
492 thresh = qsz * THRESH;
493 mthresh = qsz * MTHRESH;
494 max = base + num * qsz;
495 if (num >= THRESH)
496 {
497 qst(base, max);
498 hi = base + thresh;
499 }
500 else
501 {
502 hi = max;
503 }
504 /*
505 * First put smallest element, which must be in the first THRESH, in
506 * the first position as a sentinel. This is done just by searching
507 * the first THRESH elements (or the first n if n < THRESH), finding
508 * the min, and swapping it into the first position.
509 */
510 for (j = lo = base; (lo += qsz) < hi; )
511 if (qcmp(j, lo) > 0)
512 j = lo;
513 if (j != base)
514 {
515 /* swap j into place */
516 for (i = base, hi = base + qsz; i < hi; )
517 {
518 __XchgB__(i,j);
519 i++; j++;
520 }
521 }
522 /*
523 * With our sentinel in place, we now run the following hyper-fast
524 * insertion sort. For each remaining element, min, from [1] to [n-1],
525 * set hi to the index of the element AFTER which this one goes.
526 * Then, do the standard insertion sort shift on a character at a time
527 * basis for each element in the frob.
528 */
529 for (min = base; (hi = min += qsz) < max; )
530 {
531 while (qcmp(hi -= qsz, min) > 0)
532 /* void */;
533 if ((hi += qsz) != min) {
534 for (lo = min + qsz; --lo >= min; )
535 {
536 c = *lo;
537 for (i = j = lo; (j -= qsz) >= hi; i = j)
538 *i = *j;
539 *i = c;
540 }
541 }
542 }
543 }
544
HLFind(const void * key,void __HUGE__ * base,unsigned long nelem,unsigned width,func_compare compare)545 void __HUGE__ * __FASTCALL__ HLFind(const void *key,void __HUGE__ *base,unsigned long nelem,unsigned width,
546 func_compare compare)
547 {
548 unsigned long iter,start,end;
549 void __HUGE__ *it;
550 tCompare comp_result;
551 start = 0;
552 end = nelem;
553 iter = nelem >> 1;
554 while(1)
555 {
556 it = (char __HUGE__ *)base + iter*width;
557 comp_result = (*compare)(key,it);
558 if(!comp_result) return it;
559 if(end - start < 5) break;
560 if(comp_result > 0) start = iter;
561 else end = iter;
562 iter = start + ((end - start) >> 1L);
563 }
564 for(iter = start;iter < end;iter++)
565 {
566 it = (char __HUGE__ *)base + iter*width;
567 if(!(*compare)(key,it)) return it;
568 }
569 return NULL;
570 }
571
HLFindNearest(const void * key,void __HUGE__ * base,unsigned long nelem,unsigned width,func_compare compare)572 unsigned long __FASTCALL__ HLFindNearest(const void *key,void __HUGE__ *base,unsigned long nelem,
573 unsigned width,
574 func_compare compare)
575 {
576 unsigned long iter,start,end;
577 tCompare comp_result,comp_result2;
578 start = 0;
579 end = nelem;
580 iter = nelem >> 1;
581 while(1)
582 {
583 comp_result = (*compare)(key,(char __HUGE__ *)base + iter*width);
584 if(!comp_result) return iter;
585 if(end - start < 5) break;
586 if(comp_result > 0) start = iter;
587 else end = iter;
588 iter = start + ((end - start)>>1L);
589 }
590 for(iter = start;iter < end;iter++)
591 {
592 comp_result = (*compare)(key,(char __HUGE__ *)base + iter*width);
593 comp_result2 = iter < (nelem-1) ? (*compare)(key,(char __HUGE__ *)base + (iter+1)*width):
594 -1;
595 if(comp_result >= 0 && comp_result2 < 0) return iter;
596 }
597 return comp_result < 0 ? (start ? start - 1 : 0L)
598 : end == nelem ? nelem-1 : end;
599 }
600
601 /*
602 print message when window system is not initialized
603
604 only this function must be used for error reporting
605 (do not use printf, fprintf, etc. !)
606 */
607
printm(const char * str,...)608 int printm(const char *str,...)
609 {
610
611 #define _out_ stderr
612
613 int i;
614 va_list args;
615
616
617 va_start(args,str);
618 i = vfprintf(_out_,str,args);
619 va_end(args);
620
621 fflush(_out_);
622
623 return i;
624
625 #undef _out_
626
627 }
628
la_Build(unsigned long nitems,unsigned size_of_item,void (__FASTCALL__ * mem_out)(const char *))629 linearArray * __FASTCALL__ la_Build( unsigned long nitems, unsigned size_of_item,
630 void (__FASTCALL__ *mem_out)(const char *) )
631 {
632 linearArray * ret;
633 ret = PMalloc(sizeof(linearArray));
634 if(ret)
635 {
636 memset(ret,0,sizeof(linearArray));
637 ret->itemSize = size_of_item;
638 if(nitems)
639 {
640 ret->data = PHMalloc(nitems*size_of_item);
641 if(ret->data)
642 {
643 ret->nSize = nitems;
644 }
645 }
646 }
647 else
648 {
649 if(mem_out) (*mem_out)("Creating array");
650 }
651 return ret;
652 }
653
la_ForEach(linearArray * obj,void (__FASTCALL__ * iter_func)(void __HUGE__ *))654 void __FASTCALL__ la_ForEach(linearArray *obj,void (__FASTCALL__ *iter_func)(void __HUGE__ *))
655 {
656 unsigned long i;
657 for(i = 0;i < obj->nItems;i++)
658 {
659 (*iter_func)(((char *)obj->data)+i*obj->itemSize);
660 }
661 }
662
la_IterDestroy(linearArray * obj,void (__FASTCALL__ * del_it)(void __HUGE__ *))663 void __FASTCALL__ la_IterDestroy(linearArray *obj,void (__FASTCALL__ *del_it)(void __HUGE__ *))
664 {
665 la_ForEach(obj,del_it);
666 PHFREE(obj->data);
667 PFREE(obj);
668 }
669
la_Destroy(linearArray * obj)670 void __FASTCALL__ la_Destroy(linearArray *obj)
671 {
672 if(obj)
673 {
674 PHFREE(obj->data);
675 PFREE(obj);
676 }
677 }
678
679 #define LST_STEP 16
680
la_AddData(linearArray * obj,const void * udata,void (__FASTCALL__ * mem_out)(const char *))681 void __HUGE__* __FASTCALL__ la_AddData(linearArray *obj,const void *udata,void (__FASTCALL__ *mem_out)(const char *))
682 {
683 void __HUGE__*to;
684 if(obj->nSize > ULONG_MAX - (LST_STEP+1)) return 0;
685 if(obj->nItems + 1 > obj->nSize)
686 {
687 void *ptr;
688 if(!obj->data) ptr = PHMalloc((obj->nSize+LST_STEP)*obj->itemSize);
689 else ptr = PHRealloc(obj->data,obj->itemSize*(obj->nSize+LST_STEP));
690 if(ptr)
691 {
692 obj->nSize = obj->nSize+LST_STEP;
693 obj->data = ptr;
694 }
695 else
696 {
697 if(mem_out) (*mem_out)("Building List");
698 return NULL;
699 }
700 }
701 to = ((char __HUGE__ *)obj->data) + obj->nItems*obj->itemSize;
702 HMemCpy(to,udata,obj->itemSize);
703 obj->nItems++;
704 return to;
705 }
706
la_DeleteData(linearArray * obj,unsigned long idx)707 void __FASTCALL__ la_DeleteData(linearArray *obj,unsigned long idx) {
708 char __HUGE__ *from;
709 char __HUGE__ *to;
710 if(idx >= obj->nItems) return;
711 to = ((char __HUGE__ *)obj->data) + idx*obj->itemSize;
712 from = ((char __HUGE__ *)obj->data) + (idx+1)*obj->itemSize;
713 memmove(to,from,(obj->nItems-(idx+1))*obj->itemSize);
714 obj->nItems--;
715 }
716
la_Sort(linearArray * obj,func_compare compare)717 void __FASTCALL__ la_Sort(linearArray *obj,func_compare compare)
718 {
719 if(obj)
720 if(obj->nItems)
721 HQSort(obj->data,obj->nItems,obj->itemSize,compare);
722 }
723
la_Find(linearArray * obj,const void * key,func_compare compare)724 void __HUGE__ *__FASTCALL__ la_Find(linearArray * obj,const void *key,
725 func_compare compare)
726 {
727 void __HUGE__ * ret = NULL;
728 if(obj)
729 if(obj->nItems)
730 ret = HLFind(key,obj->data,obj->nItems,obj->itemSize,compare);
731 return ret;
732 }
733
la_FindNearest(linearArray * obj,const void * key,func_compare compare)734 unsigned long __FASTCALL__ la_FindNearest(linearArray *obj,const void *key,
735 func_compare compare)
736 {
737 unsigned long ret = 0L;
738 if(obj)
739 if(obj->nItems)
740 ret = HLFindNearest(key,obj->data,obj->nItems,obj->itemSize,compare);
741 return ret;
742 }
743