From 10fa06b998e30051431bd577ae36757cce7be200 Mon Sep 17 00:00:00 2001 From: victor Date: Thu, 17 Sep 2009 10:53:44 +0000 Subject: [PATCH 1/1] import git-svn-id: https://ttuki.vtt.fi/svn/p2p-next/p2tp@380 e16421f0-f15b-0410-abcd-98678b794739 --- .sconsign.dblite | Bin 0 -> 11203 bytes SConstruct | 14 ++ bin.cpp | 59 +++++ bin.h | 234 ++++++++++++++++++++ bin64.h | 98 +++++++++ bins.cpp | 23 ++ bins.h | 91 ++++++++ collisions.cpp | 145 ++++++++++++ congctrl.cpp | 84 +++++++ datagram.cpp | 127 +++++++++++ datagram.h | 135 ++++++++++++ do_tests.sh | 5 + doc/lancaster.txt | 27 +++ doc/p2tp-protocol.txt | 485 +++++++++++++++++++++++++++++++++++++++++ file.h | 62 ++++++ hashtree.cpp | 164 ++++++++++++++ hashtree.h | 72 ++++++ p2tp.cpp | 278 +++++++++++++++++++++++ p2tp.h | 285 ++++++++++++++++++++++++ rarest1st.cpp | 43 ++++ sbit.cpp | 254 +++++++++++++++++++++ sbit.h | 177 +++++++++++++++ sendrecv.cpp | 330 ++++++++++++++++++++++++++++ serp++.1 | 79 +++++++ tests/SConscript | 44 ++++ tests/bin64test.cpp | 53 +++++ tests/binstest.cpp | 69 ++++++ tests/bintest.cpp | 138 ++++++++++++ tests/congctrltest.cpp | 111 ++++++++++ tests/connecttest.cpp | 110 ++++++++++ tests/dgramtest.cpp | 96 ++++++++ tests/filetest.cpp | 36 +++ tests/hashtest.cpp | 69 ++++++ tests/ledbattest.cpp | 174 +++++++++++++++ tests/rwtest.cpp | 42 ++++ tests/sbit2test.cpp | 219 +++++++++++++++++++ tests/sbittest.cpp | 176 +++++++++++++++ 37 files changed, 4608 insertions(+) create mode 100644 .sconsign.dblite create mode 100644 SConstruct create mode 100644 bin.cpp create mode 100644 bin.h create mode 100644 bin64.h create mode 100644 bins.cpp create mode 100644 bins.h create mode 100644 collisions.cpp create mode 100644 congctrl.cpp create mode 100644 datagram.cpp create mode 100644 datagram.h create mode 100755 do_tests.sh create mode 100644 doc/lancaster.txt create mode 100644 doc/p2tp-protocol.txt create mode 100644 file.h create mode 100644 hashtree.cpp create mode 100644 hashtree.h create mode 100644 p2tp.cpp create mode 100644 p2tp.h create mode 100644 rarest1st.cpp create mode 100644 sbit.cpp create mode 100644 sbit.h create mode 100644 sendrecv.cpp create mode 100644 serp++.1 create mode 100644 tests/SConscript create mode 100644 tests/bin64test.cpp create mode 100644 tests/binstest.cpp create mode 100644 tests/bintest.cpp create mode 100644 tests/congctrltest.cpp create mode 100644 tests/connecttest.cpp create mode 100644 tests/dgramtest.cpp create mode 100644 tests/filetest.cpp create mode 100644 tests/hashtest.cpp create mode 100644 tests/ledbattest.cpp create mode 100644 tests/rwtest.cpp create mode 100644 tests/sbit2test.cpp create mode 100644 tests/sbittest.cpp diff --git a/.sconsign.dblite b/.sconsign.dblite new file mode 100644 index 0000000000000000000000000000000000000000..fa060ce7a0b5b6c1d0cc2768eada41f749ff1d0c GIT binary patch literal 11203 zcmdT~d6*qll@|#iga866DlV-Cd_dBveL;~xNFbdiD9KY?idbuIcb3k%-NArdK~NM# zof)^8al~D5PzT(`ec$(8XU2V>4fkb6N9K3Vt$MFs@SDtke&);fy6V1qw@&@e{ySyp zu)*+%rFwB`k?y+vqLc1&7sD&ZR6BLPhnJ_zef#LHgL2!3g}sZ@@;SG2@5=6Ate9t~QdS=auH_r^0m5XybY1MGbOB**Xi#&f zhE@;whU(~<8((_Mi~=BT(3DP6lz7NlmAyV`tqch=PQ{P{$1v z9`sa04;d&t-e7p5=zZPz&aCUxa)oC-eK1^EUBVQ-Oe-4py^rxm~|p2uyEAL!>K&*oXB&^w5Z)YDE%a=$|j0EzewXWs6uiT zVDSd>n7*N4&^Ln68o`8}M1b8|MLe8xiYlyO5Kdmjah->L?9{&Ncum|yg;%7Mv{sSM z`c5Q3$eqqK^w5C{XU@LI%`*x+D(qD>aoD&;QU^igr(h0%TeE!DmQ)|m9UfMK!&iUJLw4puNv0=l8i!Q|fsny#q8eY6%<2E`^!5lZr zgKaW&K8wUIXhl-T@C{qX%B{^p@1q!Tf!OS3Lo=PtZZS05+3c<>ZxWj=8ox}OItjuw zER!O3V<#-@BuwkLaec3(3t_W?6AHww#cnlpkyz{_*fJld00qdXz}?XhWBD5^j%XuT+}9B8PB;59*zDMgCwa-v5eH3EC2ryb zRnXK)8ToON6j9|mI4|9VDt@?npw^348bdo-E7!8@tAq;AsQLDT~O7>bgvmG-!grO;QI+^J$S|ACA+$B`q1+FIu~7 zc(;+(IznsUlo;8H)&PGxmPufi;xf}Rq48J?gwE)PhwSF z300{EAS*%12ue>jbQPoYv>r-Mo zv>x|#L(dSLt{;{jQqLTywQ7yBG5^L6t7kD*fm`H3?E6uXGSp^I;>u3=&w7hjz9di8K96(1f9Pz^tS@R zi#X`~9S5Bkch7iJ8+2a6j_^_mIx9Q-g=StRcYC>^S9EuKrJ+}KcM~I6rLN|vGE#4g z`>PGTMs9j@hx=$-PR*|s-2Wc950@_%b4$p;x3u`bu9NNcjDK2sUKM$1m3u{<_@Q3_ zzSwb*KuWiATzUiJ{|~@l5Wm&XZH)Lh*bk>d#Ka^;KJ=p8@nAf48U!`mHxH{SbOU-L zdvR>DPfv$$k{#b{=q(59&@UV}D4PN?&VeNqm0uKvmqU$yUDtt6Z^e#oU=7hmg`-BL z3H_sh`Zhyv??8Qrp?7wmb|q0-MTJ|XK^VoU7ZqWHKW<$mQQ#n%hdI5A&E12)N`2VE z{%%9>5!l~5Jl>l7=)O?r`vmp(kK@7zI;=m)SVw+}ato+SCw%Rhh7+R0#6%{ zKEzmmcrq@0L{R#up^q_2BE49;I)yP9m24J;V|Uk8kuR}iQjLFHp!kHLPj*mz%Fw4f zD1PzsTWzK-LoW#Ys7|9iibA(^)4)&j#?5OVItb`9fFexXzTbb=(B}k*&$H2gfsOu) z-NSyVHTo~J(SJpZenl4*=&K^q*9`qrC(=I~`j<|mE*QajVy8)h+Vdl1-8?SJ8WnsK zHBOlNVMSkO?VvPB<6f%$hM{kYP~Yl;c6VDS=i8#3?~Il6-A>-`v2v|XHIScf!g2TTV`u7fp z|1k8Q9S*yeBha95PwNU*dXqYJ9)w|(ltJ!CFc`0lyx2=Zx}Adq{@D!KTIo*={Zw%H z+3@bxN_)5F@bGiN;uiyT#&Ee59g2R50KHaqLE={(Hos#vR9~>ldFAkAQP$DM{GFTY_XE=D}*REGYaZSGiVsYT5 zqRulB?r-gdir>q=|6}M6ysy};#rZS%RcD#wN;3+?0~Y8G23g*;nGLr!01(cI_@v^F*wikvH0xTFogQ{5ur?d z9KOkW4XD1G{NQ+e4$xxqwbM$UfKz0Eabv1al*{gp&-wOY`yHyjhkSice2)55eG;Ed z1)N^Py3XsuEn=sDAto_u6m%>>T$Q!H7hg8n(CT~3cK5;OK!86PM@HY5&!N)K0oJZe z^_>LyCvid#K3IEYQoAU9ODFeW{E6@A`{75>I|8S*mi28*qwmjOoHx-n>jz*h(^GOE z==*^fUzpq}a+_1-RN8X=5Lp?>ifztqqobb79^BR=)_?VBa_#AI?TMK_0|$t*dJX?Q zDbs8DFYj^hOi%N%G&Xu2AKpLH4*p8e1t(#ft_AI4O?<(_fziI4TEPNY31!6!CMEhR zwFiQYi|l|bBnR4Y?TYKn-;;fVWVSJ3>k{3>r7kTPL zRUI}##%}lPp^Qm>)%edF%Tq7(B0Nn#2nV&vo%2QItA)7`aV> zBFfX}zz0ZLk@29BX_?*?yy$h8Z#kyo43yM zNGw{Xy%=WcE7`7(KeZNUjl~!r$ z>qT4*&Tu!E9w@F*dI!DIS1-wy`(;ab{$)7mT92_z(+m2E_(EL&fLz+P$og`eb*_H} zAH(&FB=Pc`8`q$5yd*$%0cr;|0%!?{=IAH!g>d~VWvgDhtc|R|Ql5+hqpy-vxIPPS zOM}}vMc`kbJ6Hu%v`st*sjKBju*9dx9@ogJ#qU~Kd8({TMC-RQG;Qb6hQz1Iwb#kD z0Osj9;K=t3{)=dRJ^yW^^$mP%qxCcS5YhTZ{AJDVpQgiyD>{ypmTecM(qY5HnJ)bk z(dtYyj%oEn5{*4teMC3@`4H=i({#k}u<7kzH~|*Lqm5M~S{v5#r&7V1m)z2uY@qG} zRqe!8nkQad1T~oBf?MLm^U$^Ay~zeRZ0U{ud=wzXs`RZ>(j3WDqni^wSXzM9hE6$X z7If-FI-rLL8`K)@U^rC*u-YxdCX9vY=TajH7{WMeK+Mr;E$e?el0+g*dxzK=G6h*< zXl*Yy&@{#ty{te^M(#Ktke89KSf+j&pdh1glmI9?IQmnZVfxUI`;=yMrj7VgVcKyD z<`9_nJj@W-7ztGLa6@NzO`{Ab5a|y&oLJ96tQ}6YE#oHxIWwiUCsoI{rXNh|=T2TCK6PCCyBN|(x9!{Z;Lz{}hRRsdL3ev<$t2%OO4B=2N zx*;td)XLFP#@sltyv)!OCuVR5WH2>3tGyf&*csdvpui3_t9nw4<(0jORo+gl%usDp zxvr~CyYrnJR9)_>^b2*LVPsS|^Nzj8K3k1?K2TKfIK%r#8n zx7);d3MGPCjFX_LFez(NOjV*Lbepn_;+U?-Hm>6*<85v*^h|!JjXh~FAPz7sZ~Ov7 zhoZ)a37tcbdk&^2WfawPBeqFG&`|tPw$$&~26~pb-?I&v`!0a@DEmnRdG4h9Jx|Dh z)?}WKY04q!0D3`dGA|r40-f`Lw}iaQ1HS7!98Nt1bXMz679NyZCHdOwD)Hw!MWH3VwjX0%%jy>7q>L)pxwPM`Jc z*jU;8^Lj&X0BH#lULn=os*qrAlk1UF-l(Fj3c2G=3hCm_a3PJ7mCR0~sN*dxrM)jK0xF=9?LPtB1_DGy0BVnI@3=Zbsi5BlG<`A@hTbemIHD zk23nPRehHy`rNY3dX`&8GEkRVC*PrNRQcF_mCaMP8~VvWAv^taxI#8#h<}zVq?(^2 zU$v8@U&v!)r1VR*r&dTazv48bkXe4MkWfk{8IrodkUYgCuE2<|3_`HIu8YYW#^k?I z$RNM9;nZ@)2kbzp4Pb{HDE$tRryD4VvVU*re>i^0%N6Y|hkUu>57?!9xk6o5D>FPB zdE<|~5+RFS;<(`ddM)A(byX&GGfO3mvuUa3$tQGB#)Ff|@s0!tM$kwYzo#BDMOuP8 z4jiGSAzp~7G)LE#+U}JFdKvmgwtXS0jgZp=C8jULv=QEU!1krSY}3P6)b;9XInT=N8$7>7; z@(Bj~RprEPRR(1e#4i4O82rLK63bKnAQN`ll1|J}8=<3F#Zpg-iq%#&gWj7un#pP- zBsE_t<*>bSJ+2%TyuXLCZABqOwYo$7C=+^Gly)E4gV`&&8@ex>SJg50Zqid(eYF12 zlGsoM6Vpam=z$Wy6ZYA(?6dVgk$;E!9lWnIVe5Po)O4L$x_MV7oHCqDDCO4A^r^U! z(p%w2!Yi}Y4X`9ppdIK4i7WQXj|bLhLDw*e+|e~m5HnBZ zq;7#08&e*PB=E9N<&`;JMXFI%`DxR{LLf6wB^0vi8Q4bN;ST0`HpyKO6_^t?`T{vU zU|(IZMtT|>Y1@KY1LJoRF}e|km|dOeVIy2{TRmu|fsJPRx2qu}1P;_6P)Ce{n-mh7 zDPbdIFP9Tqs9q=2%I2sm>@t!&KQ8sTh3Hs)!E6E%ot(w1|iaJ7T^ z<8W%t38FJ`+lkJ6Ehk7n_Tw64Cth>m_f#-!PVsVTh_{?v7o1L`nfhbj7DjiTqng;1 nGB71PFO$0xtC-(4!rOAJl6jIfrLS_VYHJiRC9sRj_fP*Xi|$W3 literal 0 HcmV?d00001 diff --git a/SConstruct b/SConstruct new file mode 100644 index 0000000..f1d6cfe --- /dev/null +++ b/SConstruct @@ -0,0 +1,14 @@ +import os +import re + +TestDir='tests' + +env = Environment(CPPPATH = ['.']) + +env.SharedLibrary ( + target='p2tp', + source = [ 'bin.cpp','hashtree.cpp','datagram.cpp', + 'sbit.cpp' ], + LIBS=['stdc++','gtest','glog','crypto'] ) + +SConscript('tests/SConscript') diff --git a/bin.cpp b/bin.cpp new file mode 100644 index 0000000..187dde4 --- /dev/null +++ b/bin.cpp @@ -0,0 +1,59 @@ +/* + * bin.cpp + * serp++ + * + * Created by Victor Grishchenko on 3/6/09. + * Copyright 2009 Delft Technical University. 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 new file mode 100644 index 0000000..3742b88 --- /dev/null +++ b/bin.h @@ -0,0 +1,234 @@ +/* + * bin.h + * serp++ + * + * Created by Victor Grishchenko on 3/6/09. + * Copyright 2009 Delft Technical University. All rights reserved. + * + */ +#ifndef BIN_H +#define BIN_H +#include +#include +#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/bin64.h b/bin64.h new file mode 100644 index 0000000..da45678 --- /dev/null +++ b/bin64.h @@ -0,0 +1,98 @@ +#ifndef BIN64_H +#define BIN64_H +#include +#include + +#include + +/** Bin numbers in the tail111 encoding: meaningless + bits in the tail are set to 0111...11, while the + head denotes the offset. Thus, 1101 is the bin + at layer 1, offset 3 (i.e. fourth). */ +struct bin64_t { + uint64_t v; + static const uint64_t NONE = 0xffffffffffffffffULL; + static const uint64_t ALL = 0x7fffffffffffffffULL; + + bin64_t() : v(NONE) {} + bin64_t(const bin64_t&b) : v(b.v) {} + bin64_t(const uint64_t val) : v(val) {} + bin64_t(uint8_t layer, uint64_t offset) : + v( (offset<<(layer+1)) | ((1ULL<>1; + } + + + int layer () const { + int r = 0; + uint64_t tail = ((v^(v+1))+1)>>1; + if (tail>0xffffffffULL) { + r = 32; + tail>>=32; + } + // courtesy of Sean Eron Anderson + // http://graphics.stanford.edu/~seander/bithacks.html + static const int DeBRUIJN[32] = { + 0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, + 31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9 + }; + r += DeBRUIJN[((uint32_t)(tail*0x077CB531U))>>27]; + return r; + } + + uint64_t base_offset () const { + return v&~(tail_bits()); + } + + uint64_t offset () const { + return v >> (layer()+1); + } + + bin64_t left () const { + assert(layer()); + return bin64_t( v ^ (tail_bit()>>1) ); + } + + bin64_t right () const { + assert(layer()); + uint64_t tb = tail_bit(); + return bin64_t( v ^ (tb|(tb>>1)) ); + } + + bin64_t parent () const { + uint64_t tbs = tail_bits(), ntbs = (tbs+1)|tbs; + return bin64_t( (v&~ntbs) | tbs ); + } + + bool is_left () const { + uint64_t tb = tail_bit(); + return !(v&(tb<<1)); + } + + /** The array must have 64 cells, as it is the max + number of peaks possible (and there are no reason + to assume there will be less in any given case. */ + static void GetPeaks(uint64_t length, bin64_t* peaks) { + int pp=0; + uint8_t layer = 0; + while (length) { + if (length&1) + peaks[pp++] = bin64_t(layer,length^1); + length>>=1; + layer++; + } + peaks[pp] = NONE; + } + +}; + + +#endif diff --git a/bins.cpp b/bins.cpp new file mode 100644 index 0000000..4dd1e3d --- /dev/null +++ b/bins.cpp @@ -0,0 +1,23 @@ +/* + * sbit.cpp + * serp++ + * + * Created by Victor Grishchenko on 4/1/09. + * Copyright 2009 Delft Technical University. All rights reserved. + * + */ +#include "bins.h" + +uint16_t bins::SPLIT[256]; +uint8_t bins::JOIN[256]; +uint16_t bins::MASK1000[32]; + +bin64_t bins::find (bin64_t range, int layer) { + // fall to left border + // do + // if up && has 0 success + // if lower && range-shift-trick + // success + // while (next && within range) + // return fail +} diff --git a/bins.h b/bins.h new file mode 100644 index 0000000..d95406f --- /dev/null +++ b/bins.h @@ -0,0 +1,91 @@ +/* + * sbit.cpp + * serp++ + * + * Created by Victor Grishchenko on 3/28/09. + * Copyright 2009 Delft Technical University. All rights reserved. + * + */ +#ifndef SERP_SBIT_H +#define SERP_SBIT_H +#include "bin64.h" + +class bins64 { + + private: + + uint32_t *bits; + uint32_t alloc_block; + + protected: + + bool join(uint32_t half) { + uint32_t cellno = bits[half]>>(half&1?16:0); + + if (deep(left) || deep(right)) // some half is deep + return false; + uint8_t b1=JOIN[cell&0xf], + b2=JOIN[(cell>>8)&0xf], + b3=JOIN[(cell>>16)&0xf], + b4=JOIN[cell>>24]; + if (b1==0xff || b2==0xff || b3==0xff || b4==0xff) + return false; + bits[half] = b1 | (b2<<4) | (b3<<8) | (b4<<12) ; + (*parentdeepcell) ^= 1<<(halfno&32); + (*childdeepcell) &= 0xffff>>1; // clean the full bit + } + + bool split(uint32_t half) { + if (deep(half)) + return false; + uint32_t cell = alloc_cell(), left=cell<<1, right=left+1; + bits[half|0xf] |= 1<<(half&0xf); + bits[left] = SPLIT[bits[half]>>8]; + bits[right] = SPLIT[bits[half&0xff]]; + bits[half] = cell; + return true; + } + + uint32_t alloc_cell () { + do{ + for(int block=alloc_block; bits[block]&(1<<32); block+=32); + for(int off=0; bits[block+off]==0 && off<31; off++); + if (off==31) + bits[block] |= 1<<32; + if (block&(1<<31)) { + bits = realloc(bits,block*2); + memset(); + } + } while (off==31); + alloc_block = block; + return block+off; + } + + public: + + class iterator { + bins64_t *host; + uint32_t back[32]; + uint32_t half; + bin64_t top; + bin64_t focus; + bin16_t mask; + public: + void left(); + void right(); + void parent(); + bin64_t next(); + bool defined(); + uint16_t& operator* (); + }; + friend class iterator; + + bool get (uint64_t bin); + + void set (uint64_t bin); + + bin64_t find (bin64_t range, int layer); + + // TODO: bitwise operators + +}; diff --git a/collisions.cpp b/collisions.cpp new file mode 100644 index 0000000..24c3173 --- /dev/null +++ b/collisions.cpp @@ -0,0 +1,145 @@ +/* + * collisions.cpp + * serp++ + * + * Created by Victor Grishchenko on 3/15/09. + * Copyright 2009 Delft Technical University. All rights reserved. + * + */ +#include "bin.h" +#include "sbit.h" +#include +#include + +using namespace std; + +#define NUMPEERS 40 +#define QUEUE_LEN 32 +#define WIDTH 20 +#define TOP (bin(WIDTH,0)) + +sbit bigpic; // common knowledge + +struct Peer { + deque packets; // packets in flight & unacknowledged + feye map; + int peerno; + bin focus; + Peer () : map(bigpic,bin(0,rand()%(1<6) + map.refocus(focus); + if (labs(map.focus-focus)>=129) + printf("bred!\n"); + map |= focus; + // sanity check + if (bigpic.get(focus)) + printf("zhopa: peer %i redid %x after jumped %i\n", + peerno,focus.offset(),oldfoc.commonParent(focus).layer()); + assert(focus.layer()==0 && focus=QUEUE_LEN) { // round trip, acks reach senders + bin packet = peers[i].packets.front(); + peers[i].packets.pop_front(); + if (packet==0) continue; + bool collision = bigpic.get(packet); + bin round = bigpic.set(packet); + printf("peer %i arrived %x filled %i coll %i\n", + i,packet.offset(),round.layer(),collision); + for(int j=0; j + +using namespace p2tp; + +CongestionControl::CongestionControl () { + state_ = SLOW_START_STATE; + cwnd_ = 1; + cainc_ = 0; + ssthresh_ = 100; + rtt_avg_ = 0; + dev_avg_ = 0; + peer_cwnd_ = 0; + data_ins_ = 0; + last_arrival_ = 0; + rate_ = TINT_1SEC/10; +} + + +void CongestionControl::RttSample (tint rtt) { + if (rtt_avg_>0) { + rtt_avg_ = (rtt_avg_*7 + rtt) >> 3; // affected by reordering + dev_avg_ = (dev_avg_*7 + ::abs(rtt-rtt_avg_)) >> 3; + } else { + rtt_avg_ = rtt; + dev_avg_ = rtt>>3; + } + DLOG(INFO)<<"sample "<=ssthresh_) + state_ = CONG_AVOID_STATE; + } else if (state_==CONG_AVOID_STATE) { + cainc_++; + if (cainc_>=cwnd_) { + cainc_ = 0; + cwnd_++; + } + } + break; + case DATA_EV: + tint interarrival = last_arrival_ ? + Datagram::now - last_arrival_ : + rtt_avg_; // starting est. corresp. cwnd==1 + last_arrival_ = Datagram::now; + if (rate_) + rate_ = ( rate_*3 + interarrival ) / 4; + else + rate_ = interarrival; + break; + } + DLOG(INFO)<<"peer irr "< rate_/2 ) // too many / + pc++; + return pc; +} + +int CongestionControl::peer_bps () const { + return 1024 * TINT_1SEC / rate_; +} diff --git a/datagram.cpp b/datagram.cpp new file mode 100644 index 0000000..3c2794a --- /dev/null +++ b/datagram.cpp @@ -0,0 +1,127 @@ +/* + * datagram.cpp + * serp++ + * + * Created by Victor Grishchenko on 3/9/09. + * Copyright 2009 Delft Technical University. All rights reserved. + * + */ +#include +#include +#include "datagram.h" + +namespace p2tp { + +tint Datagram::now = Datagram::Time(); + +int Datagram::Send () { + int r = sendto(sock,buf+offset,length-offset,0, + (struct sockaddr*)&(addr),sizeof(struct sockaddr_in)); + offset=0; + length=0; + now = Time(); + return r; +} + +int Datagram::Recv () { + socklen_t addrlen = sizeof(struct sockaddr_in); + offset = 0; + length = recvfrom (sock, buf, MAXDGRAMSZ, 0, + (struct sockaddr*)&(addr), &addrlen); + if (length<0) + PLOG(ERROR)<<"on recv"; + now = Time(); + return length; +} + + +int Datagram::Wait (int sockcnt, int* sockets, tint usec) { + LOG(INFO)<<"waiting for "<max_sock_fd) + max_sock_fd = sockets[i]; + } + int sel = select(max_sock_fd+1, &bases, NULL, &err, &timeout); + if (sel>0) { + for (int i=0; i<=sockcnt; i++) + if (FD_ISSET(sockets[i],&bases)) + return sockets[i]; + } else if (sel<0) + PLOG(ERROR)<<"select fails"; + return -1; +} + +tint Datagram::Time () { + struct timeval t; + gettimeofday(&t,NULL); + tint ret; + ret = t.tv_sec; + ret *= 1000000; + ret += t.tv_usec; + //DLOG(INFO)<<"now is "< +#include +#include +#include +#include +#include +#include +#include +//#include +#include +#include +#include +#include +#include "hashtree.h" + +namespace p2tp { + +typedef int64_t tint; +#define SEC ((tint)1000000) +#define MSEC ((tint)1000) +#define uSEC ((tint)1) +#define NEVER ((tint)0x7fffffffffffffffLL) +#define MAXDGRAMSZ 1400 + +struct Datagram { + struct sockaddr_in addr; + int sock; + int offset, length; + uint8_t buf[MAXDGRAMSZ]; + + static int Bind(int port); + static void Close(int port); + static tint Time(); + static int Wait (int sockcnt, int* sockets, tint usec=0); + static tint now; + + Datagram (int socket, struct sockaddr_in& addr_) : addr(addr_), offset(0), + length(0), sock(socket) {} + Datagram (int socket) : offset(0), length(0), sock(socket) { + memset(&addr,0,sizeof(struct sockaddr_in)); + } + + int space () const { return MAXDGRAMSZ-length; } + int size() const { return length-offset; } + std::string str() const { return std::string((char*)buf+offset,size()); } + + int Push (const uint8_t* data, int l) { // scatter-gather one day + int toc = l>32)); + *(uint32_t*)(buf+length+4) = htonl((uint32_t)(l&0xffffffff)); + length+=8; + } + void PushHash (const Sha1Hash& hash) { + Push(hash.bits, Sha1Hash::SIZE); + } + + uint8_t Pull8() { + if (size()<1) return 0; + return buf[offset++]; + } + uint16_t Pull16() { + if (size()<2) return 0; + offset+=2; + return ntohs(*(uint16_t*)(buf+offset-2)); + } + uint32_t Pull32() { + if (size()<4) return 0; + uint32_t i = ntohl(*(uint32_t*)(buf+offset)); + offset+=4; + return i; + } + uint64_t Pull64() { + if (size()<8) return 0; + uint64_t l = ntohl(*(uint32_t*)(buf+offset)); + l<<=32; + l |= ntohl(*(uint32_t*)(buf+offset+4)); + offset+=8; + return l; + } + Sha1Hash PullHash() { + if (size()