2 * differerence_cover.cpp
4 * Copyright 2003 Max-Planck-institut fuer Informatik
8 //======================================================================
9 // This file implements the computation of difference covers
10 //======================================================================
17 #include "difference_cover.hpp"
20 //----------------------------------------------------------------------
21 // Precomputed difference covers.
23 // The covers from 0 to 6 are from
24 // Luk, Wong: Two new quorum base algorithms for distributed mutual
25 // exclusion. In Proc. 17th International Conference on Distributed
26 // Computing Systems, pp. 100-106. IEEE, 1997.
27 // Covers 7 and 8 were found using an exhaustive search algorithm.
28 // All except cover 8 are known to be optimal.
29 //----------------------------------------------------------------------
31 const unsigned max_precomputed_cover = 8;
32 const unsigned coversizes[max_precomputed_cover+1] =
33 {1,2,3,4,5,7,9,13,20};
34 const unsigned cover0[] = {0};
35 const unsigned cover1[] = {0,1};
36 const unsigned cover2[] = {0,1,2};
37 const unsigned cover3[] = {0,1,2,4};
38 const unsigned cover4[] = {0,1,2,5,8};
39 const unsigned cover5[] = {0,1,2,3,7,11,19}; //{0,7,8,10,14,19,23};
40 const unsigned cover6[] = {0,1,2,5,14,16,34,42,59};
41 const unsigned cover7[] = {0,1,3,7,17,40,55,64,75,85,104,109,117};
42 const unsigned cover8[] = {0,1,3,7,12,20,30,44,65,80,89,96,114,122,
43 128,150,196,197,201,219};
44 const unsigned * covers[] = { cover0, cover1, cover2, cover3, cover4,
45 cover5, cover6, cover7, cover8 };
49 //----------------------------------------------------------------------
50 // constructor of difference_cover
52 // Constructs a difference cover modulo a power of two.
53 // (see difference_cover.hpp)
55 // Small difference covers have been precomputed (see above).
56 // Larger difference covers are computed by the algorithm in
57 // C.J. Colbourn and A.C.H. Ling. Quorums from Difference Covers.
58 // Information Processing Letters 75(1-2):9-12, 2000
59 //----------------------------------------------------------------------
60 difference_cover::difference_cover(unsigned lv)
61 : logmod(lv), mask((1<<lv)-1),
62 coverrank(1<<lv), diff2pos(1<<lv,1<<lv)
64 if (logmod <= max_precomputed_cover) {
66 // use precomputed covers
67 coversize = coversizes[logmod];
68 cover.assign(covers[logmod], covers[logmod] + coversize);
72 // use the Colbourn-Ling algorithm
75 while (24*r*r+36*r+13 < v) ++r;
77 cover.resize(coversize);
78 std::vector<unsigned>::iterator i = cover.begin();
80 std::fill(i, i+r, 1); i+=r;
82 std::fill(i, i+r, 2*r+1); i+=r;
83 std::fill(i, i+2*r+1, 4*r+3); i+=2*r+1;
84 std::fill(i, i+r+1, 2*r+2); i+=r+1;
85 std::fill(i, i+r, 1); i+=r;
86 if (i != cover.end()) {
87 throw std::logic_error("error in the Coulbourn-Ling algorithm");
89 std::partial_sum(cover.begin(), cover.end(), cover.begin());
94 std::cerr << "difference cover modulo " << (1<<logmod);
95 std::cerr << " of size " << coversize << ": " << std::endl;
96 std::copy(cover.begin(), cover.end(),
97 std::ostream_iterator<unsigned>(std::cerr, " ") );
98 std::cerr << std::endl;
101 // compute the lookup tables
102 unsigned i, j, modulus=1<<logmod;
103 for (i=0, j=0; i<modulus; ++i) {
105 if (j<coversize && cover[j] <= i) { ++j; }
107 for (i=coversize-1; i<coversize; --i) {
108 for (j=0; j<coversize; ++j) {
109 diff2pos[(cover[j]-cover[i])&mask] = cover[i];
113 // check that this is a difference cover
114 for (i=0; i<modulus; ++i) {
115 if (diff2pos[i] == modulus) {
116 throw std::logic_error("bad difference cover");
119 std::cerr << i << " = " << ((diff2pos[i]+i)&mask);
120 std::cerr << " - " << diff2pos[i];
121 std::cerr << " (mod " << modulus << ")";
122 std::cerr << std::endl;