/
vthread.cc
2045 lines (1670 loc) · 48.4 KB
/
vthread.cc
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
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
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
/*
* Copyright (c) 2001 Stephen Williams (steve@icarus.com)
*
* This source code is free software; you can redistribute it
* and/or modify it in source code form under the terms of the GNU
* General Public License as published by the Free Software
* Foundation; either version 2 of the License, or (at your option)
* any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
*/
#if !defined(WINNT)
#ident "$Id: vthread.cc,v 1.73 2002/05/27 00:53:10 steve Exp $"
#endif
# include "vthread.h"
# include "codes.h"
# include "debug.h"
# include "schedule.h"
# include "functor.h"
# include "ufunc.h"
# include "event.h"
# include "vpi_priv.h"
#ifdef HAVE_MALLOC_H
# include <malloc.h>
#endif
# include <stdlib.h>
# include <string.h>
# include <assert.h>
#include <stdio.h>
/*
* This vhtread_s structure describes all there is to know about a
* thread, including its program counter, all the private bits it
* holds, and its place in other lists.
*
*
* ** Notes On The Interactions of %fork/%join/%end:
*
* The %fork instruction creates a new thread and pushes that onto the
* stack of children for the thread. This new thread, then, becomes
* the new direct descendent of the thread. This new thread is
* therefore also the first thread to be reaped when the parent does a
* %join.
*
* It is a programming error for a thread that created threads to not
* %join as many as it created before it %ends. The linear stack for
* tracking thread relationships will create a mess otherwise. For
* example, if A creates B then C, the stack is:
*
* A --> C --> B
*
* If C then %forks X, the stack is:
*
* A --> C --> X --> B
*
* If C %ends without a join, then the stack is:
*
* A --> C(zombie) --> X --> B
*
* If A then executes 2 %joins, it will read C and X (when it ends)
* leaving B in purgatory. What's worse, A will block on the schedules
* of X and C instead of C and B, possibly creating incorrect timing.
*
* The schedule_parent_on_end flag is used by threads to tell their
* children that they are waiting for it to end. It is set by a %join
* instruction if the child is not already done. The thread that
* executes a %join instruction sets the flag in its child.
*
* The i_have_ended flag, on the other hand, is used by threads to
* tell their parents that they are already dead. A thread that
* executes %end will set its own i_have_ended flag and let its parent
* reap it when the parent does the %join. If a thread has its
* schedule_parent_on_end flag set already when it %ends, then it
* reaps itself and simply schedules its parent. If a child has its
* i_have_ended flag set when a thread executes %join, then it is free
* to reap the child immediately.
*/
struct vthread_s {
/* This is the program counter. */
unsigned long pc;
/* These hold the private thread bits. */
unsigned char *bits;
long index[4];
unsigned nbits :16;
/* My parent sets this when it wants me to wake it up. */
unsigned schedule_parent_on_end :1;
unsigned i_have_ended :1;
unsigned waiting_for_event :1;
unsigned is_scheduled :1;
/* This points to the sole child of the thread. */
struct vthread_s*child;
/* This points to my parent, if I have one. */
struct vthread_s*parent;
/* This is used for keeping wait queues. */
struct vthread_s*wait_next;
/* These are used to keep the thread in a scope. */
struct vthread_s*scope_next, *scope_prev;
};
static void thr_check_addr(struct vthread_s*thr, unsigned addr)
{
if (addr < thr->nbits)
return;
assert(addr < 0x10000);
while (thr->nbits <= addr) {
thr->bits = (unsigned char*)realloc(thr->bits, thr->nbits/4 + 16);
memset(thr->bits + thr->nbits/4, 0xaa, 16);
thr->nbits += 16*4;
}
}
static inline unsigned thr_get_bit(struct vthread_s*thr, unsigned addr)
{
assert(addr < thr->nbits);
unsigned idx = addr % 4;
addr /= 4;
return (thr->bits[addr] >> (idx*2)) & 3;
}
static inline void thr_put_bit(struct vthread_s*thr,
unsigned addr, unsigned val)
{
thr_check_addr(thr, addr);
unsigned idx = addr % 4;
addr /= 4;
unsigned mask = 3 << (idx*2);
thr->bits[addr] = (thr->bits[addr] & ~mask) | (val << (idx*2));
}
unsigned vthread_get_bit(struct vthread_s*thr, unsigned addr)
{
return thr_get_bit(thr, addr);
}
void vthread_put_bit(struct vthread_s*thr, unsigned addr, unsigned bit)
{
thr_put_bit(thr, addr, bit);
}
# define CPU_BITS (8*sizeof(unsigned long))
# define TOP_BIT (1UL << (CPU_BITS-1))
static unsigned long* vector_to_array(struct vthread_s*thr,
unsigned addr, unsigned wid)
{
unsigned awid = (wid + CPU_BITS - 1) / (8*sizeof(unsigned long));
unsigned long*val = new unsigned long[awid];
for (unsigned idx = 0 ; idx < awid ; idx += 1)
val[idx] = 0;
for (unsigned idx = 0 ; idx < wid ; idx += 1) {
unsigned long bit = thr_get_bit(thr, addr);
if (bit & 2)
goto x_out;
val[idx/CPU_BITS] |= bit << (idx % CPU_BITS);
if (addr >= 4)
addr += 1;
}
return val;
x_out:
delete[]val;
return 0;
}
/*
* Create a new thread with the given start address.
*/
vthread_t vthread_new(unsigned long pc, struct __vpiScope*scope)
{
vthread_t thr = new struct vthread_s;
thr->pc = pc;
thr->bits = (unsigned char*)malloc(16);
thr->nbits = 16*4;
thr->child = 0;
thr->parent = 0;
thr->wait_next = 0;
/* If the target scope never held a thread, then create a
header cell for it. This is a stub to make circular lists
easier to work with. */
if (scope->threads == 0) {
scope->threads = new struct vthread_s;
scope->threads->pc = 0;
scope->threads->bits = 0;
scope->threads->nbits = 0;
scope->threads->child = 0;
scope->threads->parent = 0;
scope->threads->scope_prev = scope->threads;
scope->threads->scope_next = scope->threads;
}
{ vthread_t tmp = scope->threads;
thr->scope_next = tmp->scope_next;
thr->scope_prev = tmp;
thr->scope_next->scope_prev = thr;
thr->scope_prev->scope_next = thr;
}
thr->schedule_parent_on_end = 0;
thr->is_scheduled = 0;
thr->i_have_ended = 0;
thr->waiting_for_event = 0;
thr->is_scheduled = 0;
thr_put_bit(thr, 0, 0);
thr_put_bit(thr, 1, 1);
thr_put_bit(thr, 2, 2);
thr_put_bit(thr, 3, 3);
return thr;
}
/*
* Reaping pulls the thread out of the stack of threads. If I have a
* child, then hand it over to my parent.
*/
static void vthread_reap(vthread_t thr)
{
assert(thr->wait_next == 0);
free(thr->bits);
thr->bits = 0;
if (thr->child)
thr->child->parent = thr->parent;
if (thr->parent)
thr->parent->child = thr->child;
thr->child = 0;
thr->parent = 0;
thr->scope_next->scope_prev = thr->scope_prev;
thr->scope_prev->scope_next = thr->scope_next;
thr->pc = 0;
/* If this thread is not scheduled, then is it safe to delete
it now. Otherwise, let the schedule event (which will
execute the thread at of_ZOMBIE) delete the object. */
if (thr->is_scheduled == 0)
delete thr;
}
void vthread_mark_scheduled(vthread_t thr)
{
assert(thr->is_scheduled == 0);
thr->is_scheduled = 1;
}
/*
* This function runs a thread by fetching an instruction,
* incrementing the PC, and executing the instruction.
*/
void vthread_run(vthread_t thr)
{
assert(thr->is_scheduled);
thr->is_scheduled = 0;
for (;;) {
vvp_code_t cp = codespace_index(thr->pc);
thr->pc += 1;
assert(cp);
assert(cp->opcode);
/* Run the opcode implementation. If the execution of
the opcode returns false, then the thread is meant to
be paused, so break out of the loop. */
bool rc = (cp->opcode)(thr, cp);
if (rc == false)
return;
}
}
/*
* This is called by an event functor to wake up all the threads on
* its list. I in fact created that list in the %wait instruction, and
* I also am certain that the waiting_for_event flag is set.
*/
void vthread_schedule_list(vthread_t thr)
{
while (thr) {
vthread_t tmp = thr;
thr = thr->wait_next;
assert(tmp->waiting_for_event);
tmp->waiting_for_event = 0;
tmp->wait_next = 0;
schedule_vthread(tmp, 0);
}
}
bool of_AND(vthread_t thr, vvp_code_t cp)
{
assert(cp->bit_idx[0] >= 4);
unsigned idx1 = cp->bit_idx[0];
unsigned idx2 = cp->bit_idx[1];
for (unsigned idx = 0 ; idx < cp->number ; idx += 1) {
unsigned lb = thr_get_bit(thr, idx1);
unsigned rb = thr_get_bit(thr, idx2);
if ((lb == 0) || (rb == 0)) {
thr_put_bit(thr, idx1, 0);
} else if ((lb == 1) && (rb == 1)) {
thr_put_bit(thr, idx1, 1);
} else {
thr_put_bit(thr, idx1, 2);
}
idx1 += 1;
if (idx2 >= 4)
idx2 += 1;
}
return true;
}
bool of_ADD(vthread_t thr, vvp_code_t cp)
{
assert(cp->bit_idx[0] >= 4);
unsigned long*lva = vector_to_array(thr, cp->bit_idx[0], cp->number);
unsigned long*lvb = vector_to_array(thr, cp->bit_idx[1], cp->number);
if (lva == 0 || lvb == 0)
goto x_out;
unsigned long carry;
carry = 0;
for (unsigned idx = 0 ; (idx*CPU_BITS) < cp->number ; idx += 1) {
unsigned long tmp = lvb[idx] + carry;
unsigned long sum = lva[idx] + tmp;
carry = 0;
if (tmp < lvb[idx])
carry = 1;
if (sum < tmp)
carry = 1;
if (sum < lva[idx])
carry = 1;
lva[idx] = sum;
}
for (unsigned idx = 0 ; idx < cp->number ; idx += 1) {
unsigned bit = lva[idx/CPU_BITS] >> (idx % CPU_BITS);
thr_put_bit(thr, cp->bit_idx[0]+idx, (bit&1) ? 1 : 0);
}
delete[]lva;
delete[]lvb;
return true;
x_out:
delete[]lva;
delete[]lvb;
for (unsigned idx = 0 ; idx < cp->number ; idx += 1)
thr_put_bit(thr, cp->bit_idx[0]+idx, 2);
return true;
}
bool of_ASSIGN(vthread_t thr, vvp_code_t cp)
{
unsigned char bit_val = thr_get_bit(thr, cp->bit_idx[1]);
schedule_assign(cp->iptr, bit_val, cp->bit_idx[0]);
return true;
}
bool of_ASSIGN_D(vthread_t thr, vvp_code_t cp)
{
assert(cp->bit_idx[0] < 4);
unsigned char bit_val = thr_get_bit(thr, cp->bit_idx[1]);
schedule_assign(cp->iptr, bit_val, thr->index[cp->bit_idx[0]]);
return true;
}
bool of_ASSIGN_X0(vthread_t thr, vvp_code_t cp)
{
unsigned char bit_val = thr_get_bit(thr, cp->bit_idx[1]);
vvp_ipoint_t itmp = ipoint_index(cp->iptr, thr->index[0]);
schedule_assign(itmp, bit_val, cp->bit_idx[0]);
return true;
}
bool of_ASSIGN_MEM(vthread_t thr, vvp_code_t cp)
{
unsigned char bit_val = thr_get_bit(thr, cp->bit_idx[1]);
schedule_memory(cp->mem, thr->index[3], bit_val, cp->bit_idx[0]);
return true;
}
bool of_BREAKPOINT(vthread_t thr, vvp_code_t cp)
{
#if defined(WITH_DEBUG)
breakpoint();
#endif
return true;
}
bool of_CMPS(vthread_t thr, vvp_code_t cp)
{
unsigned eq = 1;
unsigned eeq = 1;
unsigned lt = 0;
unsigned idx1 = cp->bit_idx[0];
unsigned idx2 = cp->bit_idx[1];
unsigned end1 = (idx1 < 4)? idx1 : idx1 + cp->number - 1;
unsigned end2 = (idx2 < 4)? idx2 : idx2 + cp->number - 1;
unsigned sig1 = thr_get_bit(thr, end1);
unsigned sig2 = thr_get_bit(thr, end2);
for (unsigned idx = 0 ; idx < cp->number ; idx += 1) {
unsigned lv = thr_get_bit(thr, idx1);
unsigned rv = thr_get_bit(thr, idx2);
if (lv > rv) {
lt = 0;
eeq = 0;
} else if (lv < rv) {
lt = 1;
eeq = 0;
}
if (eq != 2) {
if ((lv == 0) && (rv != 0))
eq = 0;
if ((lv == 1) && (rv != 1))
eq = 0;
if ((lv | rv) >= 2)
eq = 2;
}
if (idx1 >= 4) idx1 += 1;
if (idx2 >= 4) idx2 += 1;
}
if (eq == 2)
lt = 2;
else if ((sig1 == 1) && (sig2 == 0))
lt = 1;
else if ((sig1 == 0) && (sig2 == 1))
lt = 0;
/* Correct the lt bit to account for the sign of the parameters. */
if (lt < 2) {
sig1 = thr_get_bit(thr, end1);
sig2 = thr_get_bit(thr, end2);
/* If both numbers are negative, then switch the
direction of the lt. */
if ((sig1 == 1) && (sig2 == 1) && (eq != 0))
lt ^= 1;
/* If the first is negative and the last positive, then
a < b for certain. */
if ((sig1 == 1) && (sig2 == 0))
lt = 1;
/* If the first is positive and the last negative, then
a > b for certain. */
if ((sig1 == 0) && (sig2 == 1))
lt = 0;
}
thr_put_bit(thr, 4, eq);
thr_put_bit(thr, 5, lt);
thr_put_bit(thr, 6, eeq);
return true;
}
bool of_CMPU(vthread_t thr, vvp_code_t cp)
{
unsigned eq = 1;
unsigned eeq = 1;
unsigned lt = 0;
unsigned idx1 = cp->bit_idx[0];
unsigned idx2 = cp->bit_idx[1];
for (unsigned idx = 0 ; idx < cp->number ; idx += 1) {
unsigned lv = thr_get_bit(thr, idx1);
unsigned rv = thr_get_bit(thr, idx2);
if (lv > rv) {
lt = 0;
eeq = 0;
} else if (lv < rv) {
lt = 1;
eeq = 0;
}
if (eq != 2) {
if ((lv == 0) && (rv != 0))
eq = 0;
if ((lv == 1) && (rv != 1))
eq = 0;
if ((lv | rv) >= 2)
eq = 2;
}
if (idx1 >= 4) idx1 += 1;
if (idx2 >= 4) idx2 += 1;
}
if (eq == 2)
lt = 2;
thr_put_bit(thr, 4, eq);
thr_put_bit(thr, 5, lt);
thr_put_bit(thr, 6, eeq);
return true;
}
bool of_CMPX(vthread_t thr, vvp_code_t cp)
{
unsigned eq = 1;
unsigned idx1 = cp->bit_idx[0];
unsigned idx2 = cp->bit_idx[1];
for (unsigned idx = 0 ; idx < cp->number ; idx += 1) {
unsigned lv = thr_get_bit(thr, idx1);
unsigned rv = thr_get_bit(thr, idx2);
if ((lv < 2) && (rv < 2) && (lv != rv)) {
eq = 0;
break;
}
if (idx1 >= 4) idx1 += 1;
if (idx2 >= 4) idx2 += 1;
}
thr_put_bit(thr, 4, eq);
return true;
}
bool of_CMPZ(vthread_t thr, vvp_code_t cp)
{
unsigned eq = 1;
unsigned idx1 = cp->bit_idx[0];
unsigned idx2 = cp->bit_idx[1];
for (unsigned idx = 0 ; idx < cp->number ; idx += 1) {
unsigned lv = thr_get_bit(thr, idx1);
unsigned rv = thr_get_bit(thr, idx2);
if ((lv < 3) && (rv < 3) && (lv != rv)) {
eq = 0;
break;
}
if (idx1 >= 4) idx1 += 1;
if (idx2 >= 4) idx2 += 1;
}
thr_put_bit(thr, 4, eq);
return true;
}
bool of_DELAY(vthread_t thr, vvp_code_t cp)
{
//printf("thread %p: %%delay %lu\n", thr, cp->number);
schedule_vthread(thr, cp->number);
return false;
}
bool of_DELAYX(vthread_t thr, vvp_code_t cp)
{
unsigned long delay;
assert(cp->number < 4);
delay = thr->index[cp->number];
schedule_vthread(thr, delay);
return false;
}
/*
* Implement the %disable instruction by scanning the target scope for
* all the target threads. Kill the target threads and wake up a
* parent that is attempting a %join.
*
* XXXX BUG BUG!
* The scheduler probably still has a pointer to me, and this reaping
* will destroy this object. The result: dangling pointer.
*/
bool of_DISABLE(vthread_t thr, vvp_code_t cp)
{
struct __vpiScope*scope = (struct __vpiScope*)cp->handle;
if (scope->threads == 0)
return true;
struct vthread_s*head = scope->threads;
bool disabled_myself_flag = false;
while (head->scope_next != head) {
vthread_t tmp = head->scope_next;
/* Pull the target thread out of the scope. */
tmp->scope_next->scope_prev = tmp->scope_prev;
tmp->scope_prev->scope_next = tmp->scope_next;
/* XXXX I don't support disabling threads with children. */
assert(tmp->child == 0);
/* XXXX Don't know how to disable waiting threads. */
assert(tmp->waiting_for_event == 0);
/* If I am disabling myself, that remember that fact so
that I can finish this statement differently. */
if (tmp == thr)
disabled_myself_flag = true;
tmp->pc = 0;
tmp->i_have_ended = 1;
if (tmp->schedule_parent_on_end) {
/* If a parent is waiting in a %join, wake it up. */
assert(tmp->parent);
schedule_vthread(tmp->parent, 0, true);
vthread_reap(tmp);
} else if (tmp->parent) {
/* If the parent is yet to %join me, let its %join
do the reaping. */
//assert(tmp->is_scheduled == 0);
} else {
/* No parent at all. Goodby. */
vthread_reap(tmp);
}
}
return ! disabled_myself_flag;
}
static void divide_bits(unsigned len, unsigned char*lbits,
const unsigned char*rbits)
{
unsigned char *a, *b, *z, *t;
a = new unsigned char[len+1];
b = new unsigned char[len+1];
z = new unsigned char[len+1];
t = new unsigned char[len+1];
unsigned char carry;
unsigned char temp;
int mxa = -1, mxz = -1;
int i;
int current, copylen;
for (unsigned idx = 0 ; idx < len ; idx += 1) {
unsigned lb = lbits[idx];
unsigned rb = rbits[idx];
z[idx]=lb;
a[idx]=1-rb; // for 2s complement add..
}
z[len]=0;
a[len]=1;
for(i=0;i<(int)len+1;i++) {
b[i]=0;
}
for(i=len-1;i>=0;i--) {
if(!a[i]) {
mxa=i;
break;
}
}
for(i=len-1;i>=0;i--) {
if(z[i]) {
mxz=i;
break;
}
}
if((mxa>mxz)||(mxa==-1)) {
if(mxa==-1) {
fprintf(stderr, "Division By Zero error, exiting.\n");
exit(255);
}
goto tally;
}
copylen = mxa + 2;
current = mxz - mxa;
while(current > -1) {
carry = 1;
for(i=0;i<copylen;i++) {
temp = z[i+current] + a[i] + carry;
t[i] = (temp&1);
carry = (temp>>1);
}
if(carry) {
for(i=0;i<copylen;i++) {
z[i+current] = t[i];
}
b[current] = 1;
}
current--;
}
tally:
for (unsigned idx = 0 ; idx < len ; idx += 1) {
// n.b., z[] has the remainder...
lbits[idx] = b[idx];
}
delete []t;
delete []z;
delete []b;
delete []a;
}
bool of_DIV(vthread_t thr, vvp_code_t cp)
{
assert(cp->bit_idx[0] >= 4);
if(cp->number <= 8*sizeof(unsigned long)) {
unsigned idx1 = cp->bit_idx[0];
unsigned idx2 = cp->bit_idx[1];
unsigned long lv = 0, rv = 0;
for (unsigned idx = 0 ; idx < cp->number ; idx += 1) {
unsigned lb = thr_get_bit(thr, idx1);
unsigned rb = thr_get_bit(thr, idx2);
if ((lb | rb) & 2)
goto x_out;
lv |= lb << idx;
rv |= rb << idx;
idx1 += 1;
if (idx2 >= 4)
idx2 += 1;
}
if (rv == 0)
goto x_out;
lv /= rv;
for (unsigned idx = 0 ; idx < cp->number ; idx += 1) {
thr_put_bit(thr, cp->bit_idx[0]+idx, (lv&1) ? 1 : 0);
lv >>= 1;
}
return true;
} else {
/* Make a string of the bits of the numbers to be
divided. Then divide them, and write the results into
the thread. */
unsigned char*lbits = new unsigned char[cp->number];
unsigned char*rbits = new unsigned char[cp->number];
unsigned idx1 = cp->bit_idx[0];
unsigned idx2 = cp->bit_idx[1];
bool rval_is_zero = true;
for (unsigned idx = 0 ; idx < cp->number ; idx += 1) {
lbits[idx] = thr_get_bit(thr, idx1);
rbits[idx] = thr_get_bit(thr, idx2);
if ((lbits[idx] | rbits[idx]) > 1) {
delete[]lbits;
delete[]rbits;
goto x_out;
}
if (rbits[idx] != 0)
rval_is_zero = false;
idx1 += 1;
if (idx2 >= 4)
idx2 += 1;
}
/* Notice the special case of divide by 0. */
if (rval_is_zero) {
delete[]lbits;
delete[]rbits;
goto x_out;
}
divide_bits(cp->number, lbits, rbits);
for (unsigned idx = 0 ; idx < cp->number ; idx += 1) {
thr_put_bit(thr, cp->bit_idx[0]+idx, lbits[idx]);
}
delete[]lbits;
delete[]rbits;
return true;
}
x_out:
for (unsigned idx = 0 ; idx < cp->number ; idx += 1)
thr_put_bit(thr, cp->bit_idx[0]+idx, 2);
return true;
}
static void negate_bits(unsigned len, unsigned char*bits)
{
unsigned char carry = 1;
for (unsigned idx = 0 ; idx < len ; idx += 1) {
carry += bits[idx]? 0 : 1;
bits[idx] = carry & 1;
carry >>= 1;
}
}
bool of_DIV_S(vthread_t thr, vvp_code_t cp)
{
assert(cp->bit_idx[0] >= 4);
if(cp->number <= 8*sizeof(long)) {
unsigned idx1 = cp->bit_idx[0];
unsigned idx2 = cp->bit_idx[1];
long lv = 0, rv = 0;
unsigned lb = 0;
unsigned rb = 0;
for (unsigned idx = 0 ; idx < cp->number ; idx += 1) {
lb = thr_get_bit(thr, idx1);
rb = thr_get_bit(thr, idx2);
if ((lb | rb) & 2)
goto x_out;
lv |= (long)lb << idx;
rv |= (long)rb << idx;
idx1 += 1;
if (idx2 >= 4)
idx2 += 1;
}
/* Extend the sign to fill the native long. */
for (unsigned idx = cp->number; idx < (8*sizeof lv); idx += 1) {
lv |= (long)lb << idx;
rv |= (long)rb << idx;
}
if (rv == 0)
goto x_out;
lv /= rv;
for (unsigned idx = 0 ; idx < cp->number ; idx += 1) {
thr_put_bit(thr, cp->bit_idx[0]+idx, (lv&1) ? 1 : 0);
lv >>= 1;
}
} else {
unsigned char*lbits = new unsigned char[cp->number];
unsigned char*rbits = new unsigned char[cp->number];
unsigned idx1 = cp->bit_idx[0];
unsigned idx2 = cp->bit_idx[1];
bool rval_is_zero = true;
for (unsigned idx = 0 ; idx < cp->number ; idx += 1) {
lbits[idx] = thr_get_bit(thr, idx1);
rbits[idx] = thr_get_bit(thr, idx2);
if ((lbits[idx] | rbits[idx]) > 1) {
delete[]lbits;
delete[]rbits;
goto x_out;
}
if (rbits[idx] != 0)
rval_is_zero = false;
idx1 += 1;
if (idx2 >= 4)
idx2 += 1;
}
/* Notice the special case of divide by 0. */
if (rval_is_zero) {
delete[]lbits;
delete[]rbits;
goto x_out;
}
/* Signed division is unsigned division on the absolute
values of the operands, then corrected for the number
of signs. */
unsigned sign_flag = 0;
if (lbits[cp->number-1]) {
sign_flag += 1;
negate_bits(cp->number, lbits);
}
if (rbits[cp->number-1]) {
sign_flag += 1;
negate_bits(cp->number, rbits);
}
divide_bits(cp->number, lbits, rbits);
if (sign_flag & 1) {
negate_bits(cp->number, lbits);
}
for (unsigned idx = 0 ; idx < cp->number ; idx += 1) {
thr_put_bit(thr, cp->bit_idx[0]+idx, lbits[idx]);
}
delete[]lbits;
delete[]rbits;
}
return true;
x_out:
for (unsigned idx = 0 ; idx < cp->number ; idx += 1)
thr_put_bit(thr, cp->bit_idx[0]+idx, 2);
return true;
}
/*
* This terminates the current thread. If there is a parent who is
* waiting for me to die, then I schedule it. At any rate, I mark
* myself as a zombie by setting my pc to 0.
*
* It is possible for this thread to have children at this %end. This
* means that my child is really my sibling created by my parent, and
* my parent will do the proper %joins in due course. For example:
*
* %fork child_1, test;
* %fork child_2, test;
* ... parent code ...
* %join;
* %join;
* %end;
*
* child_1 ;
* %end;
* child_2 ;
* %end;
*
* In this example, the main thread creates threads child_1 and
* child_2. It is possible that this thread is child_2, so there is a
* parent pointer and a child pointer, even though I did no
* %forks or %joins. This means that I have a ->child pointer and a
* ->parent pointer.
*
* If the main thread has executed the first %join, then it is waiting
* for me, and I will be reaped right away.
*
* If the main thread has not executed a %join yet, then this thread
* becomes a zombie. The main thread executes its %join eventually,
* reaping me at that time.
*
* It does not matter the order that child_1 and child_2 threads call
* %end -- child_2 will be reaped by the first %join, and child_1 will
* be reaped by the second %join.
*/
bool of_END(vthread_t thr, vvp_code_t)
{