From 82a990baae0d9323092e6493cc268c0df41dcd59 Mon Sep 17 00:00:00 2001 From: Victor Grishchenko Date: Thu, 28 Jan 2010 18:50:25 +0100 Subject: [PATCH] removing historical/unused files --- bin.cpp | 59 ---------- bin.h | 241 -------------------------------------- doc/swift-protocol.txt | 2 +- sbit.cpp | 254 ----------------------------------------- sbit.h | 177 ---------------------------- 5 files changed, 1 insertion(+), 732 deletions(-) delete mode 100644 bin.cpp delete mode 100644 bin.h delete mode 100644 sbit.cpp delete mode 100644 sbit.h diff --git a/bin.cpp b/bin.cpp deleted file mode 100644 index 7511501..0000000 --- a/bin.cpp +++ /dev/null @@ -1,59 +0,0 @@ -/* - * bin.cpp - * serp++ - * - * Created by Victor Grishchenko on 3/6/09. - * Copyright 2009 Delft University of Technology. All rights reserved. - * - */ - -#include "bin.h" -#include - -bin bin::NONE = 0; -bin bin::ALL = 0x7fffffff; -uint8_t bin::BC[256] = {}; -uint8_t bin::T0[256] = {}; - -void bin::init () { - for(int i=0; i<256; i++) { - int bc=0, bit; - for(bit=0; bit<8; bit++) - if ((i>>bit)&1) bc++; - BC[i] = bc; - for(bit=0; bit<8 && ((i>>bit)&1)==0; bit++); - T0[i] = bit; - } -} - -bin::vec bin::peaks (uint32_t len) { - bin::vec pks; - uint32_t i=len, run=0; - while (i) { - uint32_t bit = bin::highbit(i); - i^=bit; - run |= bit; - pks.push_back(lenpeak(run)); - } - return pks; -} - -void bin::order (vec* vv) { - vec& v = *vv; - std::sort(v.begin(),v.end()); - std::reverse(v.begin(),v.end()); - vec::iterator pw=v.begin(), pr=v.begin(); - while (pr!=v.end()) { - *pw = *pr; - while (pw!=v.begin() && (pw-1)->sibling()==*pw) { - pw--; - *pw = pw->parent(); - } - bin skipto = *pw - pw->mass(); - while (pr!=v.end() && *pr>skipto) { - pr++; - } - pw++; - } - v.resize(pw-v.begin()); -} diff --git a/bin.h b/bin.h deleted file mode 100644 index ca1b3cc..0000000 --- a/bin.h +++ /dev/null @@ -1,241 +0,0 @@ -/* - * bin.h - * serp++ - * - * Created by Victor Grishchenko on 3/6/09. - * Copyright 2009 Delft University of Technology. All rights reserved. - * - */ -#ifndef BIN_H -#define BIN_H -#include -#ifdef _MSC_VER - // To avoid complaints about std::max. Appears to work in VS2008 - #undef min - #undef max - #include "compat/stdint.h" -#else - #include -#endif -#include - -struct bin { - uint32_t b; - - static bin NONE; - static bin ALL; - static uint8_t BC[256]; - static uint8_t T0[256]; - - bin() : b(0) {} - bin(const bin& b_) : b(b_.b) {} - bin(uint32_t b_) : b(b_) {} - - bin(uint8_t layer_, uint32_t offset) { - b = lenpeak((offset+1)<>=16; - if ( (i&0xff)==0 ) - ret +=8, i>>=8; - return ret+T0[i&0xff]; - } - - static uint8_t bitcount (uint32_t i) { - //uint8_t* p = (uint8_t*) &i; - //return BC[p[0]] + BC[p[1]] + BC[p[2]] + BC[p[3]]; - return BC[i&0xff] + - BC[(i>>8)&0xff] + - BC[(i>>16)&0xff] + - BC[i>>24]; - } - - static uint32_t blackout (uint32_t i) { - return i|=(i|=(i|=(i|=(i|=i>>1)>>2)>>4)>>8)>>16; - } - - static uint32_t highbit (uint32_t i) { - return (blackout(i)+1)>>1; - } - - static bool all1 (uint32_t a) { - return !(a&(a+1)); - } - - static bin lenpeak (uint32_t length) { - return (length<<1) - bitcount(length); - } - - static uint8_t lenlayer (uint32_t len) { - return tailzeros(len); - } - - static bin layermass (uint8_t layer) { - return (2< vec; - static vec peaks (uint32_t len); - - static void order (vec* v); - - operator uint32_t() const { return b; } - - bin operator ++ () { return b++; } - bin operator -- () { return b--; } - bin operator ++ (int) { return ++b; } - bin operator -- (int) { return --b; } - - uint32_t mlat() const { - return 0; - } - - bin left() const { - return bin(b-(mass()>>1)-1); - } - - bin right() const { - return bin(b-1); - } - - bin right_foot() const { - return bin(b-layer()); - } - - bin left_foot() const { - return bin(b-mass()+1); - } - - uint32_t length() const { - //assert(*this<=ALL); - uint32_t apx = (b>>1) + 16; //if (b<=ALL-32) apx = ALL>>1; - uint32_t next = apx-8; - next = apx = lenpeak(next)>=b ? next : apx; - next -= 4; - next = apx = lenpeak(next)>=b ? next : apx; - next -= 2; - next = apx = lenpeak(next)>=b ? next : apx; - next -= 1; - next = apx = lenpeak(next)>=b ? next : apx; - return apx; - } - - uint32_t mass() const { - return layermass(layer()); - } - - uint8_t layer() const { - uint32_t len = length(); - uint8_t topeak = lenpeak(len) - b; - return lenlayer(len) - topeak; - } - - uint32_t width () const { - return 1<>ls) +1; - uint8_t newlr = std::max(0,layer()-ls); - return lenpeak(newlen) - lenlayer(newlen) + newlr; - } - - uint32_t offset () const { - return length() - width(); - } - - bin modulo (uint8_t ls) const { - if (layer()>=ls) - return layermass(ls); - bin blockleft = lenpeak(((length()-1) & ~((1<b-mass(); - } - - bin commonParent (bin other) const { - uint8_t maxlayer = std::max(layer(),other.layer()); - uint32_t myoff = offset()>>maxlayer, othoff = other.offset()>>maxlayer; - uint32_t diff = blackout(myoff^othoff); - uint8_t toshift = bitcount(diff); - return bin(maxlayer+toshift,myoff>>toshift); - } - - bin child (bin dir) const { - return left().contains(dir) ? left() : right(); - } - - bin parent (uint8_t g=1) const { - uint32_t l = length(); - uint8_t h2b = layer()+g; - uint32_t pbit = 1<parent()==b+1; - } - - bool is_left () const { - return !is_right(); - } - - bin sibling () const { - return is_left() ? bin(b+mass()) : bin(b-mass()); - } - - bin scoped (bin top, uint8_t height) const { - assert(layer()<=top.layer()); // TERRIBLE - assert(top.layer()>=height); - uint8_t rel_layer; - if (layer()+height>=top.layer()) - rel_layer = layer()+height-top.layer(); - else - rel_layer = 0;//top.layer() - height; - uint32_t rel_offset = (offset()-top.offset()) >> (top.layer()-height+rel_layer); - return bin(rel_layer,rel_offset); - } - - bin unscoped (bin top, uint8_t height) const { - uint32_t undermass = layermass(top.layer()-height); - uint32_t pad = (1<b) + pad - undermass*pad; - } - -} ; - - -uint8_t bitcount (uint32_t num); - -/*bin l=b>a.b?a.b:b, g=b>a.b?b:a.b; - while (!g.contains(l)) - g = g.parent(); - return g;*/ - -#endif -//20 mln ops per second diff --git a/doc/swift-protocol.txt b/doc/swift-protocol.txt index 11597de..c978dd7 100644 --- a/doc/swift-protocol.txt +++ b/doc/swift-protocol.txt @@ -577,7 +577,7 @@ Table of Contents root hash is supplied in the handshake message, the crypto scheme in use will be known from the very beginning. As the root hash is the identifier, different schemes of crypto cannot be mixed in the - same swarms, but different swarms may distribute the same content + same swarm, but different swarms may distribute the same content using different crypto. diff --git a/sbit.cpp b/sbit.cpp deleted file mode 100644 index a03715e..0000000 --- a/sbit.cpp +++ /dev/null @@ -1,254 +0,0 @@ -/* - * sbit.cpp - * serp++ - * - * Created by Victor Grishchenko on 4/1/09. - * Copyright 2009 Delft University of Technology. All rights reserved. - * - */ -#include "sbit.h" - -uint16_t bins::SPLIT[256]; -uint8_t bins::JOIN[256]; -uint16_t bins::OFFMASK[32]; -static uint16_t NO_PARENT = 0xffff; - -bins::bins () : peak(31), bits(32,0), deep(32,false), prnt(16,NO_PARENT), - allocp(1), rescan_flag(true) { - prnt[0] = 0; - deep[1] = true; -} - -bins::bins(const bins& b) : peak(b.peak), allocp(b.allocp), - bits(b.bits), prnt(b.prnt), deep(b.deep), rescan_flag(b.rescan_flag) -{ -} - - - -void bins::init () { - for(int i=0; i<256; i++) - JOIN[i] = 0xff; - for(int i=0; i<256; i++) { - int split = 0; - for(int b=0; b<8; b++) - if (i&(1<peak) - return false; - chunk_iterator i(const_cast(this)); - while (i.deep() && i.chunk_top()>pos) - i.to(pos); - if (i.deep()) - return false; - int l = OFFMASK[pos.scoped(i.chunk_top(),4)]; - return (*i & l) == l; -} - - -bool bins::clean(bin pos) const { - if (pos>peak) - return bin::all1(pos) ? clean(peak) : true; - chunk_iterator i(const_cast(this)); - while (i.deep() && i.chunk_top()>pos) - i.to(pos); - if (i.deep()) - return false; - int l = OFFMASK[pos.scoped(i.chunk_top(),4)]; - return (*i & l) == 0; -} - - -void bins::expand () { - int oldrootcell = cell_alloc(); - if (deep[0]) - prnt[bits[0]] = oldrootcell; - prnt[oldrootcell] = 0; - int orl = oldrootcell<<1, orr = orl+1; - bits[orl] = bits[0]; - bits[orr] = 0; - bits[0] = oldrootcell; - deep[orl] = deep[0]; - deep[orr] = false; - deep[0] = true; - peak = peak.parent(); - compact(0); -} - - -void bins::set (bin pos, bool to) { - if (!pos) - return; - while (pos>peak) - expand(); - chunk_iterator i(this); - while (i.chunk_top().layer()>pos.layer()+4) - i.to(pos); - while (i.deep() && i.chunk_top().layer()>pos.layer()) - i.to(pos); - if (i.deep()) - unlink(i.half); - int mask = OFFMASK[pos.scoped(i.chunk_top(),4)]; - if (to) - *i |= mask; - else - *i &= ~mask; - while(i.up()); //compact -} - - -bool bins::compact (int half) { - if (!deep[half]) - return false; - int l = bits[half]<<1, r = l+1; - if (deep[l] || deep[r]) - return false; - int l1 = JOIN[bits[l]&0xff], l2 = JOIN[bits[l]>>8]; - if (l1==0xff || l2==0xff) - return false; - int r1 = JOIN[bits[r]&0xff], r2 = JOIN[bits[r]>>8]; - if (r1==0xff || r2==0xff) - return false; - deep[half] = false; - prnt[bits[half]] = NO_PARENT; - deep[l] = deep[r] = false;//coward - bits[half] = (l1) | (l2<<4) | (r1<<8) | (r2<<12); - return true; -} - - -void bins::split (int half) { - if (!deep[half]) { - int newcell = cell_alloc(), oldcell=half>>1; - int l = newcell<<1, r = l+1; - bits[l] = SPLIT[bits[half]&0xff]; - bits[r] = SPLIT[bits[half]>>8]; - deep[half] = true; - bits[half] = newcell; - prnt[newcell] = oldcell; - } -} - - -void bins::doop (bins& b, int op) { - while (b.peakpeak) - expand(); - chunk_iterator i(this), j(&b); - do { - while (i.deep() || j.deep()) { - i.left(); - j.left(); - } - switch (op) { - case OR_OP: (*i) |= *j; break; - case AND_OP: (*i) &= *j; break; - case SUB_OP: (*i) &= ~*j; break; - } - while (i.chunk_top().is_right()) { - i.up(); - j.up(); - } - i.up(); - j.up(); - i.right(); - j.right(); - } while (!i.end()); -} - - -void bins::operator |= (bins& b) { - doop(b,OR_OP); -} - - -void bins::operator &= (bins& b) { - doop(b,AND_OP); -} - - -void bins::operator -= (bins& b) { - doop(b,SUB_OP); -} - - - -int bins::cell_alloc () { // FIXME: 0xffff size too big - while (allocp renames(allocp), irenames(allocp); - int newcellsize=0; - for(int i=0; i>1, rn=ln+1; - deep[l] = deep[ln]; - deep[r] = deep[rn]; - prnt[i] = irenames[prnt[n]]; - bits[l] = deep[l] ? irenames[bits[ln]] : bits[ln]; - bits[r] = deep[r] ? irenames[bits[rn]] : bits[rn]; - } - allocp = newcellsize; - } - if (allocp>bits.size()/2) { - deep.resize(bits.size()*2); - prnt.resize(bits.size()); - bits.resize(bits.size()*2); - } - }*/ \ No newline at end of file diff --git a/sbit.h b/sbit.h deleted file mode 100644 index 06cfd59..0000000 --- a/sbit.h +++ /dev/null @@ -1,177 +0,0 @@ -/* - * sbit.cpp - * serp++ - * - * Created by Victor Grishchenko on 3/28/09. - * Copyright 2009 Delft University of Technology. All rights reserved. - * - */ -#ifndef SERP_SBIT_H -#define SERP_SBIT_H -#include -#include "bin.h" - -class bins { - -public: - - class bin_iterator; - - /** Traverses 16-bit chunks. */ - class chunk_iterator { - bins* host; - bin top; - int half; - - bool up() { - top=top.parent(); - int cell = half>>1; - half=host->prnt[cell]<<1; - if (!host->deep[half] || host->bits[half]!=cell) - half++; - assert(host->deep[half] && host->bits[half]==cell); - return host->compact(half); - } - void left() { - assert(top.layer()>4); - top = top.left(); - if (!deep()) - host->split(half); - half = host->bits[half]<<1; - } - void right() { - assert(top.layer()>4); - top = top.right(); - if (!deep()) - host->split(half); - half = (host->bits[half]<<1)+1; - } - void to(bin target) { - assert(top.layer()>4); - bin next = top.child(target); - if (next.is_left()) - left(); - else - right(); - } - int cell () const { return half>>1; } - bool deep() const { return host->deep[half]; } - bool is_right () const { return half&1; } - bool end () const { return half==1; } - - public: - chunk_iterator(bins* h, int hlf=0) : host(h), top(h->peak), half(hlf) { - //while (deep()) - // left(); - } - void operator ++ () { - while (is_right()) - up(); - up(); - right(); - while (deep() && !end()) - left(); - } - uint16_t& operator * () { - return host->bits[half]; - } - bool operator == (const bins::chunk_iterator& b) const { - return host==b.host && half==b.half; - } - bin chunk_top() const { return top; } - friend class bins::bin_iterator; - friend class bins; - }; // chunk_iterator - - - /** Traverses bins. */ - class bin_iterator { - bins::chunk_iterator i; - bin cur; - public: - bin_iterator(chunk_iterator ci, bin pos=0) : i(ci), cur(pos) { - while (!i.end() && i.deep()) - i.left(); - ++(*this); - } - bin operator * () const { - return cur.unscoped(i.top,4); - } - void operator ++ () { - if (i.end()) - return; - do { - if (cur bits; - std::vector prnt; // BAD BAD BAD - std::vector deep; - int allocp; - bool rescan_flag; - - -private: - - void unlink (int half); - void expand(); - void split(int half); - - //void make_space(); - int cell_alloc(); - bool compact (int cell); - - void doop (bins& b, int op); - - static uint16_t SPLIT[256]; - static uint8_t JOIN[256]; - static uint16_t OFFMASK[32]; - typedef enum { AND_OP, OR_OP, SUB_OP } ops_t; - -public: - - bins(); - bins(const bins& orig); - - bool get(bin pos) const; - bool clean(bin pos) const; - bool contains(bin pos) const { return get(pos); } - void set(bin pos, bool to=true); - bool empty() const { return !deep[0] && !bits[0]; } - bool operator [] (bin pos) const {return get(pos);} - void operator |= (bin pos) { set(pos); } - void operator -= (bin pos) { set(pos,false); } - void operator |= (bins& b); - void operator &= (bins& b); - void operator -= (bins& b); - - bin_iterator begin() { return bin_iterator(chunk_iterator(this,0)); } - bin_iterator end() { return bin_iterator(chunk_iterator(this,1),1); } - - static void init(); - friend class SbitTest; - -}; - - -#endif \ No newline at end of file -- 2.20.1