Changeset 781


Ignore:
Timestamp:
Dec 5, 2010, 4:13:58 PM (8 years ago)
Author:
cameron
Message:

SIMD_CARRY_Q

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/lib/carryQ.h

    r778 r781  
    22// carryQ.h
    33// Robert D. Cameron
     4// Dec. 5, 2010 - first queuing implementation
    45// November 29, 2010 - first version without actual queueing.
    56//
    67
     8#ifndef SIMD_CARRY_Q
    79#include "block_carry.h"
     10
    811
    912#define CarryQtype CarryType *
     
    9598  }
    9699}
    97 
     100#endif
     101#ifdef SIMD_CARRY_Q
     102
     103#define CarryQtype SIMD_type
     104
     105#define CarryDeclare(name, count)\
     106  CarryQtype name
     107
     108#define CarryInit(name, count)\
     109  name = simd_const_1(0)
     110
     111SIMD_type carryQ_ci_mask = sisd_from_int(1);
     112SIMD_type carryQ_co_mask = sisd_slli(carryQ_ci_mask, 127);
     113
     114#define carryQ_adc128(x, y, carryQ,  sum) \
     115do{ \
     116  SIMD_type gen = simd_and(x, y); \
     117  SIMD_type prop = simd_or(x, y); \
     118  SIMD_type partial = simd_add_64(simd_add_64(x, y), simd_and(carryQ, carryQ_ci_mask)); \
     119  carryQ = simd_srli_64(carryQ, 1); \
     120  SIMD_type c1 = sisd_slli(simd_srli_64(simd_or(gen, simd_andc(prop, partial)), 63), 64); \
     121  sum = simd_add_64(c1, partial); \
     122  carryQ = simd_or(carryQ, simd_and(simd_or(gen, simd_andc(prop, sum)), carryQ_co_mask)); \
     123} while(0)
     124
     125#define carryQ_sbb128(x, y, carryQ, difference) \
     126do {\
     127  SIMD_type gen = simd_andc(y, x); \
     128  SIMD_type prop = simd_not(simd_xor(x, y)); \
     129  SIMD_type partial = simd_sub_64(simd_sub_64(x, y), simd_and(carryQ, carryQ_ci_mask)); \
     130  carryQ = simd_srli_64(carryQ, 1); \
     131  SIMD_type b1 = sisd_slli(simd_srli_64(simd_or(gen, simd_and(prop, partial)), 63), 64); \
     132  difference = simd_sub_64(partial, b1); \
     133  carryQ = simd_or(carryQ, simd_and(simd_or(gen, simd_andc(prop, difference)), carryQ_co_mask)); \
     134}while(0)
     135
     136#define carryQ_advance_with_carry(cursor, carryQ, rslt)\
     137do {\
     138  SIMD_type carry_out = simd_and(cursor, carryQ_co_mask);\
     139  SIMD_type carry_in = simd_and(carryQ, carryQ_ci_mask);\
     140  carryQ = simd_or(simd_srli_64(carryQ, 1), carry_out); \
     141  SIMD_type shift_out = simd_srli_64(cursor, 63);\
     142  SIMD_type low_bits = simd_mergel_64(shift_out, carry_in);\
     143  rslt = simd_or(simd_add_64(cursor, cursor), low_bits);\
     144} while(0)
     145
     146static inline BitBlock BitBlock_advance_ci_co(BitBlock strm, CarryQtype & cq, int carryno) {
     147 BitBlock rslt;
     148 carryQ_advance_with_carry(strm, cq, rslt);
     149 return rslt;
     150}
     151
     152static inline BitBlock BitBlock_advance_co(BitBlock strm, CarryQtype & cq, int carryno) {
     153 BitBlock rslt;
     154 carryQ_advance_with_carry(strm, cq, rslt);
     155 return rslt;
     156}
     157
     158static inline BitBlock BitBlock_add_ci_co(BitBlock strm1, BitBlock strm2, CarryQtype & cq, int carryno) {
     159 BitBlock sum;
     160 carryQ_adc128(strm1, strm2, cq, sum);
     161 return sum;
     162}
     163
     164static inline BitBlock BitBlock_add_co(BitBlock strm1, BitBlock strm2, CarryQtype & cq, int carryno) {
     165 BitBlock sum;
     166 carryQ_adc128(strm1, strm2, cq, sum);
     167 return sum;
     168}
     169
     170static inline BitBlock BitBlock_sub_ci_co(BitBlock strm1, BitBlock strm2, CarryQtype & cq, int carryno) {
     171 BitBlock diff;
     172 carryQ_sbb128(strm1, strm2, cq, diff);
     173 return diff;
     174}
     175
     176static inline BitBlock BitBlock_sub_co(BitBlock strm1, BitBlock strm2, CarryQtype & cq, int carryno) {
     177 BitBlock diff;
     178 carryQ_sbb128(strm1, strm2, cq, diff);
     179 return diff;
     180}
     181
     182static inline BitBlock BitBlock_scanthru_ci_co(BitBlock markers0, BitBlock charclass, CarryQtype & cq, int carryno) {
     183 BitBlock markers1;
     184 carryQ_adc128(markers0, charclass, cq, markers1);
     185 return simd_andc(markers1, charclass);
     186}
     187
     188static inline BitBlock BitBlock_scanthru_co(BitBlock markers0, BitBlock charclass, CarryQtype & cq, int carryno) {
     189 BitBlock markers1;
     190 carryQ_adc128(markers0, charclass, cq, markers1);
     191 return simd_andc(markers1, charclass);
     192}
     193
     194typedef union {SIMD_type bitblock; uint64_t int64[2];} BitBlock_int64;
     195
     196static inline bool CarryTest(CarryQtype cq, int carryno, int carry_count) {
     197  BitBlock_int64 t;
     198  t.bitblock = cq;
     199  uint64_t carryQ_top_N_mask = ((1 << carry_count) -1);
     200  return t.int64[0] & carryQ_top_N_mask;
     201}
     202
     203static inline void CarryDequeueEnqueue(CarryQtype & cq, int carryno, int carry_count) {
     204  // Given carryin queue with carry_count carries starting from carryno are 0,
     205  // ensure that the carryout queue has carry_count carries starting from carryno set to 0.
     206  cq = sisd_srli(cq, carry_count);
     207}
     208
     209static inline void CarryCombine(CarryQtype & cq, CarryQtype local_cq, int carryno, int carry_count) {
     210  cq = simd_or(cq, local_cq);
     211}
     212
     213static inline void CarryQ_Adjust(CarryQtype & cq, int carry_count) {
     214  // Adjust the carryQ so that carries enqueued are readied for dequeiing.
     215  cq = sisd_srli(cq, (128-carry_count));
     216}
     217
     218
     219#endif
Note: See TracChangeset for help on using the changeset viewer.