sqlcipher/src/bitvec.c at Xcode5 · securitykernel/sqlcipher · GitHub

History

407 lines (387 loc) · 12.8 KB

Raw

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

336

337

338

339

340

341

342

343

344

345

346

347

348

349

350

351

352

353

354

355

356

357

358

359

360

361

362

363

364

365

366

367

368

369

370

371

372

373

374

375

376

377

378

379

380

381

382

383

384

385

386

387

388

389

390

391

392

393

394

395

396

397

398

399

400

401

402

403

404

405

406

407

** 2008 February 16

** The author disclaims copyright to this source code. In place of

** a legal notice, here is a blessing:

** May you do good and not evil.

** May you find forgiveness for yourself and forgive others.

** May you share freely, never taking more than you give.

*************************************************************************

** This file implements an object that represents a fixed-length

** bitmap. Bits are numbered starting with 1.

** A bitmap is used to record which pages of a database file have been

** journalled during a transaction, or which pages have the "dont-write"

** property. Usually only a few pages are meet either condition.

** So the bitmap is usually sparse and has low cardinality.

** But sometimes (for example when during a DROP of a large table) most

** or all of the pages in a database can get journalled. In those cases,

** the bitmap becomes dense with high cardinality. The algorithm needs

** to handle both cases well.

** The size of the bitmap is fixed when the object is created.

** All bits are clear when the bitmap is created. Individual bits

** may be set or cleared one at a time.

** Test operations are about 100 times more common that set operations.

** Clear operations are exceedingly rare. There are usually between

** 5 and 500 set operations per Bitvec object, though the number of sets can

** sometimes grow into tens of thousands or larger. The size of the

** Bitvec object is the number of pages in the database file at the

** start of a transaction, and is thus usually less than a few thousand,

** but can be as large as 2 billion for a really big database.

#include "sqliteInt.h"

/* Size of the Bitvec structure in bytes. */

#define BITVEC_SZ 512

/* Round the union size down to the nearest pointer boundary, since that's how

** it will be aligned within the Bitvec struct. */

#define BITVEC_USIZE (((BITVEC_SZ-(3*sizeof(u32)))/sizeof(Bitvec*))*sizeof(Bitvec*))

/* Type of the array "element" for the bitmap representation.

** Should be a power of 2, and ideally, evenly divide into BITVEC_USIZE.

** Setting this to the "natural word" size of your CPU may improve

** performance. */

#define BITVEC_TELEM u8

/* Size, in bits, of the bitmap element. */

#define BITVEC_SZELEM 8

/* Number of elements in a bitmap array. */

#define BITVEC_NELEM (BITVEC_USIZE/sizeof(BITVEC_TELEM))

/* Number of bits in the bitmap array. */

#define BITVEC_NBIT (BITVEC_NELEM*BITVEC_SZELEM)

/* Number of u32 values in hash table. */

#define BITVEC_NINT (BITVEC_USIZE/sizeof(u32))

/* Maximum number of entries in hash table before

** sub-dividing and re-hashing. */

#define BITVEC_MXHASH (BITVEC_NINT/2)

/* Hashing function for the aHash representation.

** Empirical testing showed that the *37 multiplier

** (an arbitrary prime)in the hash function provided

** no fewer collisions than the no-op *1. */

#define BITVEC_HASH(X) (((X)*1)%BITVEC_NINT)

#define BITVEC_NPTR (BITVEC_USIZE/sizeof(Bitvec *))

** A bitmap is an instance of the following structure.

** This bitmap records the existence of zero or more bits

** with values between 1 and iSize, inclusive.

** There are three possible representations of the bitmap.

** If iSize<=BITVEC_NBIT, then Bitvec.u.aBitmap[] is a straight

** bitmap. The least significant bit is bit 1.

** If iSize>BITVEC_NBIT and iDivisor==0 then Bitvec.u.aHash[] is

** a hash table that will hold up to BITVEC_MXHASH distinct values.

** Otherwise, the value i is redirected into one of BITVEC_NPTR

** sub-bitmaps pointed to by Bitvec.u.apSub[]. Each subbitmap

** handles up to iDivisor separate values of i. apSub[0] holds

** values between 1 and iDivisor. apSub[1] holds values between

** iDivisor+1 and 2*iDivisor. apSub[N] holds values between

** N*iDivisor+1 and (N+1)*iDivisor. Each subbitmap is normalized

** to hold deal with values between 1 and iDivisor.

struct Bitvec {

u32 iSize; /* Maximum bit index. Max iSize is 4,294,967,296. */

u32 nSet; /* Number of bits that are set - only valid for aHash

** element. Max is BITVEC_NINT. For BITVEC_SZ of 512,

** this would be 125. */

u32 iDivisor; /* Number of bits handled by each apSub[] entry. */

/* Should >=0 for apSub element. */

/* Max iDivisor is max(u32) / BITVEC_NPTR + 1. */

/* For a BITVEC_SZ of 512, this would be 34,359,739. */

union {

BITVEC_TELEM aBitmap[BITVEC_NELEM]; /* Bitmap representation */

u32 aHash[BITVEC_NINT]; /* Hash table representation */

Bitvec *apSub[BITVEC_NPTR]; /* Recursive representation */

} u;

};

** Create a new bitmap object able to handle bits between 0 and iSize,

** inclusive. Return a pointer to the new object. Return NULL if

** malloc fails.

Bitvec *sqlite3BitvecCreate(u32 iSize){

Bitvec *p;

assert( sizeof(*p)==BITVEC_SZ );

p = sqlite3MallocZero( sizeof(*p) );

if( p ){

p->iSize = iSize;

}

return p;

}

** Check to see if the i-th bit is set. Return true or false.

** If p is NULL (if the bitmap has not been created) or if

** i is out of range, then return false.

int sqlite3BitvecTest(Bitvec *p, u32 i){

if( p==0 ) return 0;

if( i>p->iSize || i==0 ) return 0;

i--;

while( p->iDivisor ){

u32 bin = i/p->iDivisor;

i = i%p->iDivisor;

p = p->u.apSub[bin];

if (!p) {

return 0;

}

if( p->iSize<=BITVEC_NBIT ){

return (p->u.aBitmap[i/BITVEC_SZELEM] & (1<<(i&(BITVEC_SZELEM-1))))!=0;

} else{

u32 h = BITVEC_HASH(i++);

while( p->u.aHash[h] ){

if( p->u.aHash[h]==i ) return 1;

h = (h+1) % BITVEC_NINT;

}

return 0;

}

** Set the i-th bit. Return 0 on success and an error code if

** anything goes wrong.

** This routine might cause sub-bitmaps to be allocated. Failing

** to get the memory needed to hold the sub-bitmap is the only

** that can go wrong with an insert, assuming p and i are valid.

** The calling function must ensure that p is a valid Bitvec object

** and that the value for "i" is within range of the Bitvec object.

** Otherwise the behavior is undefined.

int sqlite3BitvecSet(Bitvec *p, u32 i){

u32 h;

if( p==0 ) return SQLITE_OK;

assert( i>0 );

assert( i<=p->iSize );

i--;

while((p->iSize > BITVEC_NBIT) && p->iDivisor) {

u32 bin = i/p->iDivisor;

i = i%p->iDivisor;

if( p->u.apSub[bin]==0 ){

p->u.apSub[bin] = sqlite3BitvecCreate( p->iDivisor );

if( p->u.apSub[bin]==0 ) return SQLITE_NOMEM;

}

p = p->u.apSub[bin];

}

if( p->iSize<=BITVEC_NBIT ){

p->u.aBitmap[i/BITVEC_SZELEM] |= 1 << (i&(BITVEC_SZELEM-1));

return SQLITE_OK;

}

h = BITVEC_HASH(i++);

/* if there wasn't a hash collision, and this doesn't */

/* completely fill the hash, then just add it without */

/* worring about sub-dividing and re-hashing. */

if( !p->u.aHash[h] ){

if (p->nSet<(BITVEC_NINT-1)) {

goto bitvec_set_end;

} else {

goto bitvec_set_rehash;

}

/* there was a collision, check to see if it's already */

/* in hash, if not, try to find a spot for it */

do {

if( p->u.aHash[h]==i ) return SQLITE_OK;

h++;

if( h>=BITVEC_NINT ) h = 0;

} while( p->u.aHash[h] );

/* we didn't find it in the hash. h points to the first */

/* available free spot. check to see if this is going to */

/* make our hash too "full". */

bitvec_set_rehash:

if( p->nSet>=BITVEC_MXHASH ){

unsigned int j;

int rc;

u32 *aiValues = sqlite3StackAllocRaw(0, sizeof(p->u.aHash));

if( aiValues==0 ){

return SQLITE_NOMEM;

}else{

memcpy(aiValues, p->u.aHash, sizeof(p->u.aHash));

memset(p->u.apSub, 0, sizeof(p->u.apSub));

p->iDivisor = (p->iSize + BITVEC_NPTR - 1)/BITVEC_NPTR;

rc = sqlite3BitvecSet(p, i);

for(j=0; j<BITVEC_NINT; j++){

if( aiValues[j] ) rc |= sqlite3BitvecSet(p, aiValues[j]);

}

sqlite3StackFree(0, aiValues);

return rc;

}

bitvec_set_end:

p->nSet++;

p->u.aHash[h] = i;

return SQLITE_OK;

}

** Clear the i-th bit.

** pBuf must be a pointer to at least BITVEC_SZ bytes of temporary storage

** that BitvecClear can use to rebuilt its hash table.

void sqlite3BitvecClear(Bitvec *p, u32 i, void *pBuf){

if( p==0 ) return;

assert( i>0 );

i--;

while( p->iDivisor ){

u32 bin = i/p->iDivisor;

i = i%p->iDivisor;

p = p->u.apSub[bin];

if (!p) {

return;

}

if( p->iSize<=BITVEC_NBIT ){

p->u.aBitmap[i/BITVEC_SZELEM] &= ~(1 << (i&(BITVEC_SZELEM-1)));

}else{

unsigned int j;

u32 *aiValues = pBuf;

memcpy(aiValues, p->u.aHash, sizeof(p->u.aHash));

memset(p->u.aHash, 0, sizeof(p->u.aHash));

p->nSet = 0;

for(j=0; j<BITVEC_NINT; j++){

if( aiValues[j] && aiValues[j]!=(i+1) ){

u32 h = BITVEC_HASH(aiValues[j]-1);

p->nSet++;

while( p->u.aHash[h] ){

h++;

if( h>=BITVEC_NINT ) h = 0;

}

p->u.aHash[h] = aiValues[j];

}

** Destroy a bitmap object. Reclaim all memory used.

void sqlite3BitvecDestroy(Bitvec *p){

if( p==0 ) return;

if( p->iDivisor ){

unsigned int i;

for(i=0; i<BITVEC_NPTR; i++){

sqlite3BitvecDestroy(p->u.apSub[i]);

}

sqlite3_free(p);

}

** Return the value of the iSize parameter specified when Bitvec *p

** was created.

u32 sqlite3BitvecSize(Bitvec *p){

return p->iSize;

}

#ifndef SQLITE_OMIT_BUILTIN_TEST

** Let V[] be an array of unsigned characters sufficient to hold

** up to N bits. Let I be an integer between 0 and N. 0<=I<N.

** Then the following macros can be used to set, clear, or test

** individual bits within V.

#define SETBIT(V,I) V[I>>3] |= (1<<(I&7))

#define CLEARBIT(V,I) V[I>>3] &= ~(1<<(I&7))

#define TESTBIT(V,I) (V[I>>3]&(1<<(I&7)))!=0

** This routine runs an extensive test of the Bitvec code.

** The input is an array of integers that acts as a program

** to test the Bitvec. The integers are opcodes followed

** by 0, 1, or 3 operands, depending on the opcode. Another

** opcode follows immediately after the last operand.

** There are 6 opcodes numbered from 0 through 5. 0 is the

** "halt" opcode and causes the test to end.

** 0 Halt and return the number of errors

** 1 N S X Set N bits beginning with S and incrementing by X

** 2 N S X Clear N bits beginning with S and incrementing by X

** 3 N Set N randomly chosen bits

** 4 N Clear N randomly chosen bits

** 5 N S X Set N bits from S increment X in array only, not in bitvec

** The opcodes 1 through 4 perform set and clear operations are performed

** on both a Bitvec object and on a linear array of bits obtained from malloc.

** Opcode 5 works on the linear array only, not on the Bitvec.

** Opcode 5 is used to deliberately induce a fault in order to

** confirm that error detection works.

** At the conclusion of the test the linear array is compared

** against the Bitvec object. If there are any differences,

** an error is returned. If they are the same, zero is returned.

** If a memory allocation error occurs, return -1.

int sqlite3BitvecBuiltinTest(int sz, int *aOp){

Bitvec *pBitvec = 0;

unsigned char *pV = 0;

int rc = -1;

int i, nx, pc, op;

void *pTmpSpace;

/* Allocate the Bitvec to be tested and a linear array of

** bits to act as the reference */

pBitvec = sqlite3BitvecCreate( sz );

pV = sqlite3MallocZero( (sz+7)/8 + 1 );

pTmpSpace = sqlite3_malloc(BITVEC_SZ);

if( pBitvec==0 || pV==0 || pTmpSpace==0 ) goto bitvec_end;

/* NULL pBitvec tests */

sqlite3BitvecSet(0, 1);

sqlite3BitvecClear(0, 1, pTmpSpace);

/* Run the program */

pc = 0;

while( (op = aOp[pc])!=0 ){

switch( op ){

case 1:

case 2:

case 5: {

nx = 4;

i = aOp[pc+2] - 1;

aOp[pc+2] += aOp[pc+3];

break;

}

case 3:

case 4:

default: {

nx = 2;

sqlite3_randomness(sizeof(i), &i);

break;

}

if( (--aOp[pc+1]) > 0 ) nx = 0;

pc += nx;

i = (i & 0x7fffffff)%sz;

if( (op & 1)!=0 ){

SETBIT(pV, (i+1));

if( op!=5 ){

if( sqlite3BitvecSet(pBitvec, i+1) ) goto bitvec_end;

}

}else{

CLEARBIT(pV, (i+1));

sqlite3BitvecClear(pBitvec, i+1, pTmpSpace);

}

/* Test to make sure the linear array exactly matches the

** Bitvec object. Start with the assumption that they do

** match (rc==0). Change rc to non-zero if a discrepancy

** is found.

rc = sqlite3BitvecTest(0,0) + sqlite3BitvecTest(pBitvec, sz+1)

+ sqlite3BitvecTest(pBitvec, 0)

+ (sqlite3BitvecSize(pBitvec) - sz);

for(i=1; i<=sz; i++){

if( (TESTBIT(pV,i))!=sqlite3BitvecTest(pBitvec,i) ){

rc = i;

break;

}

/* Free allocated structure */

bitvec_end:

sqlite3_free(pTmpSpace);

sqlite3_free(pV);

sqlite3BitvecDestroy(pBitvec);

return rc;

}

#endif /* SQLITE_OMIT_BUILTIN_TEST */

sqlcipher/src/bitvec.c at Xcode5 · securitykernel/sqlcipher · GitHub

Expand file tree

Breadcrumbs

bitvec.c

Latest commit

History

Breadcrumbs

bitvec.c

File metadata and controls