hashfn.c Source File (original) (raw)

46#define UINT32_ALIGN_MASK (sizeof(uint32) - 1)

48#define rot(x,k) pg_rotate_left32(x, k)

82#define mix(a,b,c) \

83{ \

84 a -= c; a ^= rot(c, 4); c += b; \

85 b -= a; b ^= rot(a, 6); a += c; \

86 c -= b; c ^= rot(b, 8); b += a; \

87 a -= c; a ^= rot(c,16); c += b; \

88 b -= a; b ^= rot(a,19); a += c; \

89 c -= b; c ^= rot(b, 4); b += a; \

90}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116#define final(a,b,c) \

117{ \

118 c ^= b; c -= rot(b,14); \

119 a ^= c; a -= rot(c,11); \

120 b ^= a; b -= rot(a,25); \

121 c ^= b; c -= rot(b,16); \

122 a ^= c; a -= rot(c, 4); \

123 b ^= a; b -= rot(a,14); \

124 c ^= b; c -= rot(b,24); \

125}

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

147{

149 b,

150 c,

152

153

154 len = keylen;

155 a = b = c = 0x9e3779b9 + len + 3923095;

156

157

159 {

160

162

163

164 while (len >= 12)

165 {

166 a += ka[0];

167 b += ka[1];

168 c += ka[2];

170 ka += 3;

171 len -= 12;

172 }

173

174

175 k = (const unsigned char *) ka;

176#ifdef WORDS_BIGENDIAN

177 switch (len)

178 {

179 case 11:

180 c += ((uint32) k[10] << 8);

181

182 case 10:

183 c += ((uint32) k[9] << 16);

184

185 case 9:

186 c += ((uint32) k[8] << 24);

187

188 case 8:

189

190 b += ka[1];

191 a += ka[0];

192 break;

193 case 7:

194 b += ((uint32) k[6] << 8);

195

196 case 6:

197 b += ((uint32) k[5] << 16);

198

199 case 5:

200 b += ((uint32) k[4] << 24);

201

202 case 4:

203 a += ka[0];

204 break;

205 case 3:

206 a += ((uint32) k[2] << 8);

207

208 case 2:

209 a += ((uint32) k[1] << 16);

210

211 case 1:

212 a += ((uint32) k[0] << 24);

213

214 }

215#else

216 switch (len)

217 {

218 case 11:

219 c += ((uint32) k[10] << 24);

220

221 case 10:

222 c += ((uint32) k[9] << 16);

223

224 case 9:

225 c += ((uint32) k[8] << 8);

226

227 case 8:

228

229 b += ka[1];

230 a += ka[0];

231 break;

232 case 7:

233 b += ((uint32) k[6] << 16);

234

235 case 6:

236 b += ((uint32) k[5] << 8);

237

238 case 5:

239 b += k[4];

240

241 case 4:

242 a += ka[0];

243 break;

244 case 3:

245 a += ((uint32) k[2] << 16);

246

247 case 2:

248 a += ((uint32) k[1] << 8);

249

250 case 1:

251 a += k[0];

252

253 }

254#endif

255 }

256 else

257 {

258

259

260

261 while (len >= 12)

262 {

263#ifdef WORDS_BIGENDIAN

264 a += (k[3] + ((uint32) k[2] << 8) + ((uint32) k[1] << 16) + ((uint32) k[0] << 24));

265 b += (k[7] + ((uint32) k[6] << 8) + ((uint32) k[5] << 16) + ((uint32) k[4] << 24));

266 c += (k[11] + ((uint32) k[10] << 8) + ((uint32) k[9] << 16) + ((uint32) k[8] << 24));

267#else

268 a += (k[0] + ((uint32) k[1] << 8) + ((uint32) k[2] << 16) + ((uint32) k[3] << 24));

269 b += (k[4] + ((uint32) k[5] << 8) + ((uint32) k[6] << 16) + ((uint32) k[7] << 24));

270 c += (k[8] + ((uint32) k[9] << 8) + ((uint32) k[10] << 16) + ((uint32) k[11] << 24));

271#endif

273 k += 12;

274 len -= 12;

275 }

276

277

278#ifdef WORDS_BIGENDIAN

279 switch (len)

280 {

281 case 11:

282 c += ((uint32) k[10] << 8);

283

284 case 10:

285 c += ((uint32) k[9] << 16);

286

287 case 9:

288 c += ((uint32) k[8] << 24);

289

290 case 8:

291

292 b += k[7];

293

294 case 7:

295 b += ((uint32) k[6] << 8);

296

297 case 6:

298 b += ((uint32) k[5] << 16);

299

300 case 5:

301 b += ((uint32) k[4] << 24);

302

303 case 4:

304 a += k[3];

305

306 case 3:

307 a += ((uint32) k[2] << 8);

308

309 case 2:

310 a += ((uint32) k[1] << 16);

311

312 case 1:

313 a += ((uint32) k[0] << 24);

314

315 }

316#else

317 switch (len)

318 {

319 case 11:

320 c += ((uint32) k[10] << 24);

321

322 case 10:

323 c += ((uint32) k[9] << 16);

324

325 case 9:

326 c += ((uint32) k[8] << 8);

327

328 case 8:

329

330 b += ((uint32) k[7] << 24);

331

332 case 7:

333 b += ((uint32) k[6] << 16);

334

335 case 6:

336 b += ((uint32) k[5] << 8);

337

338 case 5:

339 b += k[4];

340

341 case 4:

342 a += ((uint32) k[3] << 24);

343

344 case 3:

345 a += ((uint32) k[2] << 16);

346

347 case 2:

348 a += ((uint32) k[1] << 8);

349

350 case 1:

351 a += k[0];

352

353 }

354#endif

355 }

356

357 final(a, b, c);

358

359

360 return c;

361}

362

363

364

365

366

367

368

369

370

373{

375 b,

376 c,

378

379

380 len = keylen;

381 a = b = c = 0x9e3779b9 + len + 3923095;

382

383

384 if (seed != 0)

385 {

386

387

388

389

390

391 a += (uint32) (seed >> 32);

394 }

395

396

398 {

399

401

402

403 while (len >= 12)

404 {

405 a += ka[0];

406 b += ka[1];

407 c += ka[2];

409 ka += 3;

410 len -= 12;

411 }

412

413

414 k = (const unsigned char *) ka;

415#ifdef WORDS_BIGENDIAN

416 switch (len)

417 {

418 case 11:

419 c += ((uint32) k[10] << 8);

420

421 case 10:

422 c += ((uint32) k[9] << 16);

423

424 case 9:

425 c += ((uint32) k[8] << 24);

426

427 case 8:

428

429 b += ka[1];

430 a += ka[0];

431 break;

432 case 7:

433 b += ((uint32) k[6] << 8);

434

435 case 6:

436 b += ((uint32) k[5] << 16);

437

438 case 5:

439 b += ((uint32) k[4] << 24);

440

441 case 4:

442 a += ka[0];

443 break;

444 case 3:

445 a += ((uint32) k[2] << 8);

446

447 case 2:

448 a += ((uint32) k[1] << 16);

449

450 case 1:

451 a += ((uint32) k[0] << 24);

452

453 }

454#else

455 switch (len)

456 {

457 case 11:

458 c += ((uint32) k[10] << 24);

459

460 case 10:

461 c += ((uint32) k[9] << 16);

462

463 case 9:

464 c += ((uint32) k[8] << 8);

465

466 case 8:

467

468 b += ka[1];

469 a += ka[0];

470 break;

471 case 7:

472 b += ((uint32) k[6] << 16);

473

474 case 6:

475 b += ((uint32) k[5] << 8);

476

477 case 5:

478 b += k[4];

479

480 case 4:

481 a += ka[0];

482 break;

483 case 3:

484 a += ((uint32) k[2] << 16);

485

486 case 2:

487 a += ((uint32) k[1] << 8);

488

489 case 1:

490 a += k[0];

491

492 }

493#endif

494 }

495 else

496 {

497

498

499

500 while (len >= 12)

501 {

502#ifdef WORDS_BIGENDIAN

503 a += (k[3] + ((uint32) k[2] << 8) + ((uint32) k[1] << 16) + ((uint32) k[0] << 24));

504 b += (k[7] + ((uint32) k[6] << 8) + ((uint32) k[5] << 16) + ((uint32) k[4] << 24));

505 c += (k[11] + ((uint32) k[10] << 8) + ((uint32) k[9] << 16) + ((uint32) k[8] << 24));

506#else

507 a += (k[0] + ((uint32) k[1] << 8) + ((uint32) k[2] << 16) + ((uint32) k[3] << 24));

508 b += (k[4] + ((uint32) k[5] << 8) + ((uint32) k[6] << 16) + ((uint32) k[7] << 24));

509 c += (k[8] + ((uint32) k[9] << 8) + ((uint32) k[10] << 16) + ((uint32) k[11] << 24));

510#endif

512 k += 12;

513 len -= 12;

514 }

515

516

517#ifdef WORDS_BIGENDIAN

518 switch (len)

519 {

520 case 11:

521 c += ((uint32) k[10] << 8);

522

523 case 10:

524 c += ((uint32) k[9] << 16);

525

526 case 9:

527 c += ((uint32) k[8] << 24);

528

529 case 8:

530

531 b += k[7];

532

533 case 7:

534 b += ((uint32) k[6] << 8);

535

536 case 6:

537 b += ((uint32) k[5] << 16);

538

539 case 5:

540 b += ((uint32) k[4] << 24);

541

542 case 4:

543 a += k[3];

544

545 case 3:

546 a += ((uint32) k[2] << 8);

547

548 case 2:

549 a += ((uint32) k[1] << 16);

550

551 case 1:

552 a += ((uint32) k[0] << 24);

553

554 }

555#else

556 switch (len)

557 {

558 case 11:

559 c += ((uint32) k[10] << 24);

560

561 case 10:

562 c += ((uint32) k[9] << 16);

563

564 case 9:

565 c += ((uint32) k[8] << 8);

566

567 case 8:

568

569 b += ((uint32) k[7] << 24);

570

571 case 7:

572 b += ((uint32) k[6] << 16);

573

574 case 6:

575 b += ((uint32) k[5] << 8);

576

577 case 5:

578 b += k[4];

579

580 case 4:

581 a += ((uint32) k[3] << 24);

582

583 case 3:

584 a += ((uint32) k[2] << 16);

585

586 case 2:

587 a += ((uint32) k[1] << 8);

588

589 case 1:

590 a += k[0];

591

592 }

593#endif

594 }

595

596 final(a, b, c);

597

598

599 return ((uint64) b << 32) | c;

600}

601

602

603

604

605

606

607

608

611{

613 b,

614 c;

615

616 a = b = c = 0x9e3779b9 + (uint32) sizeof(uint32) + 3923095;

617 a += k;

618

619 final(a, b, c);

620

621

622 return c;

623}

624

625

626

627

628

629

632{

634 b,

635 c;

636

637 a = b = c = 0x9e3779b9 + (uint32) sizeof(uint32) + 3923095;

638

639 if (seed != 0)

640 {

641 a += (uint32) (seed >> 32);

644 }

645

646 a += k;

647

648 final(a, b, c);

649

650

651 return ((uint64) b << 32) | c;

652}

653

654

655

656

657

658

661{

662

663

664

665

666

667 Size s_len = strlen((const char *) key);

668

669 s_len = Min(s_len, keysize - 1);

670 return hash_bytes((const unsigned char *) key, (int) s_len);

671}

672

673

674

675

678{

679 return hash_bytes((const unsigned char *) key, (int) keysize);

680}

681

682

683

684

685

686

689{

692}

uint32 hash_bytes_uint32(uint32 k)

uint64 hash_bytes_extended(const unsigned char *k, int keylen, uint64 seed)

uint32 hash_bytes(const unsigned char *k, int keylen)

uint32 tag_hash(const void *key, Size keysize)

uint64 hash_bytes_uint32_extended(uint32 k, uint64 seed)

#define UINT32_ALIGN_MASK

uint32 uint32_hash(const void *key, Size keysize)

uint32 string_hash(const void *key, Size keysize)

Assert(PointerIsAligned(start, uint64))