-
+ 4998CC0716B4CBD3D0E8EAB6B254DE811C9D25601E4AE86C17215E5D66096E9D5768C2CFA2312A1AE9FC460A943A9536F88ED72ADC69B46BD9FCBD15F3D6E0FBffa/libffa/fz_qshft.adb(0 . 0)(1 . 233)
500 ------------------------------------------------------------------------------
501 ------------------------------------------------------------------------------
502 -- This file is part of 'Finite Field Arithmetic', aka 'FFA'. --
503 -- --
504 -- (C) 2018 Stanislav Datskovskiy ( www.loper-os.org ) --
505 -- http://wot.deedbot.org/17215D118B7239507FAFED98B98228A001ABFFC7.html --
506 -- --
507 -- You do not have, nor can you ever acquire the right to use, copy or --
508 -- distribute this software ; Should you use this software for any purpose, --
509 -- or copy and distribute it to anyone or in any manner, you are breaking --
510 -- the laws of whatever soi-disant jurisdiction, and you promise to --
511 -- continue doing so for the indefinite future. In any case, please --
512 -- always : read and understand any software ; verify any PGP signatures --
513 -- that you use - for any purpose. --
514 -- --
515 -- See also http://trilema.com/2015/a-new-software-licensing-paradigm . --
516 ------------------------------------------------------------------------------
517 ------------------------------------------------------------------------------
518
519 with Iron; use Iron;
520 with Word_Ops; use Word_Ops;
521 with W_Pred; use W_Pred;
522 with W_Shifts; use W_Shifts;
523 with FZ_Basic; use FZ_Basic;
524 with FZ_Shift; use FZ_Shift;
525
526
527 package body FZ_QShft is
528
529 -- Constant-time subword shift, for where there is no barrel shifter
530 procedure FZ_Quiet_ShiftRight_SubW_Soft(N : in FZ;
531 ShiftedN : in out FZ;
532 Count : in WBit_Index) is
533 Nw : constant Word := Word(Count);
534 nC : constant WBool := W_ZeroP(Nw); -- 'no carry' for Count == 0 case
535 Ni : Word := 0; -- Current word
536 C : Word := 0; -- Current carry
537 S : Positive; -- Current shiftness level
538 B : Word; -- Quantity of shift (bitwalked over)
539 CB : Word; -- Quantity of carry counter-shift (bitwalked over)
540 St : Word; -- Temporary word shift candidate
541 Ct : Word; -- Temporary carry counter-shift candidate
542 begin
543 for i in reverse N'Range loop
544 Ni := N(i);
545 ShiftedN(i) := C;
546 C := W_Mux(Ni, 0, nC);
547 S := 1;
548 B := Nw;
549 CB := Word(Bitness) - B;
550 -- For each shift level (of the subword shiftvalue width) :
551 for j in 1 .. BitnessLog2 loop
552 -- Shift and mux the current word
553 St := Shift_Right(Ni, S);
554 Ni := W_Mux(Ni, St, B and 1);
555 -- Shift and mux the current carry
556 Ct := Shift_Left(C, S);
557 C := W_Mux(C, Ct, CB and 1);
558 -- Go to the next shiftness level
559 S := S * 2;
560 B := Shift_Right(B, 1);
561 CB := Shift_Right(CB, 1);
562 end loop;
563 -- Slide in the carry from the previous shift
564 ShiftedN(i) := ShiftedN(i) or Ni;
565 end loop;
566 end FZ_Quiet_ShiftRight_SubW_Soft;
567
568
569 -- Constant-time subword shift, for where there is no barrel shifter
570 procedure FZ_Quiet_ShiftLeft_SubW_Soft(N : in FZ;
571 ShiftedN : in out FZ;
572 Count : in WBit_Index) is
573 Nw : constant Word := Word(Count);
574 nC : constant WBool := W_ZeroP(Nw); -- 'no carry' for Count == 0 case
575 Ni : Word := 0; -- Current word
576 C : Word := 0; -- Current carry
577 S : Positive; -- Current shiftness level
578 B : Word; -- Quantity of shift (bitwalked over)
579 CB : Word; -- Quantity of carry counter-shift (bitwalked over)
580 St : Word; -- Temporary word shift candidate
581 Ct : Word; -- Temporary carry counter-shift candidate
582 begin
583 for i in N'Range loop
584 Ni := N(i);
585 ShiftedN(i) := C;
586 C := W_Mux(Ni, 0, nC);
587 S := 1;
588 B := Nw;
589 CB := Word(Bitness) - B;
590 -- For each shift level (of the subword shiftvalue width) :
591 for j in 1 .. BitnessLog2 loop
592 -- Shift and mux the current word
593 St := Shift_Left(Ni, S);
594 Ni := W_Mux(Ni, St, B and 1);
595 -- Shift and mux the current carry
596 Ct := Shift_Right(C, S);
597 C := W_Mux(C, Ct, CB and 1);
598 -- Go to the next shiftness level
599 S := S * 2;
600 B := Shift_Right(B, 1);
601 CB := Shift_Right(CB, 1);
602 end loop;
603 -- Slide in the carry from the previous shift
604 ShiftedN(i) := ShiftedN(i) or Ni;
605 end loop;
606 end FZ_Quiet_ShiftLeft_SubW_Soft;
607
608
609 -- Constant-time arbitrary Right-Shift.
610 procedure FZ_Quiet_ShiftRight(N : in FZ;
611 ShiftedN : in out FZ;
612 Count : in FZBit_Index) is
613
614 -- Total number of bit positions to shift by
615 C : constant Word := Word(Count);
616
617 -- Number of sub-Word bit positions to shift by
618 Bits : constant Natural := Natural(C and (2**BitnessLog2 - 1));
619
620 -- The Bitness of N's Length
621 Wb : constant Positive := FZ_Bitness_Log2(N);
622
623 -- Number of whole-Word bitnesses to shift by
624 Words : Word := Shift_Right(C, BitnessLog2);
625
626 -- Current 'shiftness level'
627 S : Indices := 1;
628
629 begin
630
631 -- Subword shift first:
632 if HaveBarrelShifter then
633 -- If permitted, use iron shifter:
634 FZ_ShiftRight(N, ShiftedN, Bits);
635 else
636 -- Otherwise, use the soft subword shifter:
637 FZ_Quiet_ShiftRight_SubW_Soft(N, ShiftedN, Bits);
638 end if;
639
640 -- Then whole-Word shift:
641 for i in 1 .. Wb loop
642
643 declare
644
645 -- Current bit of Words
646 WordsBit : constant WBool := Words and 1;
647
648 begin
649
650 -- Shift at the current shiftness
651 for i in ShiftedN'First .. ShiftedN'Last - S loop
652 ShiftedN(i) := W_Mux(ShiftedN(i), ShiftedN(i + S), WordsBit);
653 end loop;
654
655 -- Fill the emptiness
656 for i in ShiftedN'Last - S + 1 .. ShiftedN'Last loop
657 ShiftedN(i) := W_Mux(ShiftedN(i), 0, WordsBit);
658 end loop;
659
660 -- Go to the next shiftness level
661 S := S * 2;
662 Words := Shift_Right(Words, 1);
663
664 end;
665
666 end loop;
667
668 end FZ_Quiet_ShiftRight;
669
670
671 -- Constant-time arbitrary Left-Shift.
672 procedure FZ_Quiet_ShiftLeft(N : in FZ;
673 ShiftedN : in out FZ;
674 Count : in FZBit_Index) is
675
676 -- Total number of bit positions to shift by
677 C : constant Word := Word(Count);
678
679 -- Number of sub-Word bit positions to shift by
680 Bits : constant Natural := Natural(C and (2**BitnessLog2 - 1));
681
682 -- The Bitness of N's Length
683 Wb : constant Positive := FZ_Bitness_Log2(N);
684
685 -- Number of whole-Word bitnesses to shift by
686 Words : Word := Shift_Right(C, BitnessLog2);
687
688 -- Current 'shiftness level'
689 S : Indices := 1;
690
691 begin
692
693 -- Subword shift first:
694 if HaveBarrelShifter then
695 -- If permitted, use iron shifter:
696 FZ_ShiftLeft(N, ShiftedN, Bits);
697 else
698 -- Otherwise, use the soft subword shifter:
699 FZ_Quiet_ShiftLeft_SubW_Soft(N, ShiftedN, Bits);
700 end if;
701
702 -- Then whole-Word shift:
703 for i in 1 .. Wb loop
704
705 declare
706
707 -- Current bit of Words
708 WordsBit : constant WBool := Words and 1;
709
710 begin
711
712 -- Shift at the current shiftness
713 for i in reverse ShiftedN'First + S .. ShiftedN'Last loop
714 ShiftedN(i) := W_Mux(ShiftedN(i), ShiftedN(i - S), WordsBit);
715 end loop;
716
717 -- Fill the emptiness
718 for i in ShiftedN'First .. ShiftedN'First + S - 1 loop
719 ShiftedN(i) := W_Mux(ShiftedN(i), 0, WordsBit);
720 end loop;
721
722 -- Go to the next shiftness level
723 S := S * 2;
724 Words := Shift_Right(Words, 1);
725
726 end;
727
728 end loop;
729
730 end FZ_Quiet_ShiftLeft;
731
732 end FZ_QShft;