OLD | NEW |
1 // Copyright (c) 2013 The Chromium Authors. All rights reserved. | 1 // Copyright (c) 2013 The Chromium Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "net/quic/crypto/strike_register.h" | 5 #include "net/quic/crypto/strike_register.h" |
6 | 6 |
7 #include "base/logging.h" | 7 #include "base/logging.h" |
8 | 8 |
9 using std::pair; | 9 using std::pair; |
10 using std::set; | 10 using std::set; |
(...skipping 74 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
85 horizon_valid_(startup == DENY_REQUESTS_AT_STARTUP) { | 85 horizon_valid_(startup == DENY_REQUESTS_AT_STARTUP) { |
86 memcpy(orbit_, orbit, sizeof(orbit_)); | 86 memcpy(orbit_, orbit, sizeof(orbit_)); |
87 | 87 |
88 ValidateStrikeRegisterConfig(max_entries); | 88 ValidateStrikeRegisterConfig(max_entries); |
89 internal_nodes_ = new InternalNode[max_entries]; | 89 internal_nodes_ = new InternalNode[max_entries]; |
90 external_nodes_.reset(new uint8[kExternalNodeSize * max_entries]); | 90 external_nodes_.reset(new uint8[kExternalNodeSize * max_entries]); |
91 | 91 |
92 Reset(); | 92 Reset(); |
93 } | 93 } |
94 | 94 |
95 StrikeRegister::~StrikeRegister() { delete[] internal_nodes_; } | 95 StrikeRegister::~StrikeRegister() { |
| 96 delete[] internal_nodes_; |
| 97 } |
96 | 98 |
97 void StrikeRegister::Reset() { | 99 void StrikeRegister::Reset() { |
98 // Thread a free list through all of the internal nodes. | 100 // Thread a free list through all of the internal nodes. |
99 internal_node_free_head_ = 0; | 101 internal_node_free_head_ = 0; |
100 for (unsigned i = 0; i < max_entries_ - 1; i++) | 102 for (unsigned i = 0; i < max_entries_ - 1; i++) |
101 internal_nodes_[i].SetNextPtr(i + 1); | 103 internal_nodes_[i].SetNextPtr(i + 1); |
102 internal_nodes_[max_entries_ - 1].SetNextPtr(kNil); | 104 internal_nodes_[max_entries_ - 1].SetNextPtr(kNil); |
103 | 105 |
104 // Also thread a free list through the external nodes. | 106 // Also thread a free list through the external nodes. |
105 external_node_free_head_ = 0; | 107 external_node_free_head_ = 0; |
(...skipping 157 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
263 CHECK_EQ(free_external_nodes.count(i), 0u); | 265 CHECK_EQ(free_external_nodes.count(i), 0u); |
264 free_external_nodes.insert(i); | 266 free_external_nodes.insert(i); |
265 } | 267 } |
266 | 268 |
267 set<uint32> used_external_nodes; | 269 set<uint32> used_external_nodes; |
268 set<uint32> used_internal_nodes; | 270 set<uint32> used_internal_nodes; |
269 | 271 |
270 if (internal_node_head_ != kNil && | 272 if (internal_node_head_ != kNil && |
271 ((internal_node_head_ >> 8) & kExternalFlag) == 0) { | 273 ((internal_node_head_ >> 8) & kExternalFlag) == 0) { |
272 vector<pair<unsigned, bool> > bits; | 274 vector<pair<unsigned, bool> > bits; |
273 ValidateTree(internal_node_head_ >> 8, -1, bits, free_internal_nodes, | 275 ValidateTree(internal_node_head_ >> 8, |
274 free_external_nodes, &used_internal_nodes, | 276 -1, |
| 277 bits, |
| 278 free_internal_nodes, |
| 279 free_external_nodes, |
| 280 &used_internal_nodes, |
275 &used_external_nodes); | 281 &used_external_nodes); |
276 } | 282 } |
277 } | 283 } |
278 | 284 |
279 // static | 285 // static |
280 uint32 StrikeRegister::TimeFromBytes(const uint8 d[4]) { | 286 uint32 StrikeRegister::TimeFromBytes(const uint8 d[4]) { |
281 return static_cast<uint32>(d[0]) << 24 | | 287 return static_cast<uint32>(d[0]) << 24 | static_cast<uint32>(d[1]) << 16 | |
282 static_cast<uint32>(d[1]) << 16 | | 288 static_cast<uint32>(d[2]) << 8 | static_cast<uint32>(d[3]); |
283 static_cast<uint32>(d[2]) << 8 | | |
284 static_cast<uint32>(d[3]); | |
285 } | 289 } |
286 | 290 |
287 uint32 StrikeRegister::ExternalTimeToInternal(uint32 external_time) { | 291 uint32 StrikeRegister::ExternalTimeToInternal(uint32 external_time) { |
288 return external_time - internal_epoch_; | 292 return external_time - internal_epoch_; |
289 } | 293 } |
290 | 294 |
291 uint32 StrikeRegister::BestMatch(const uint8 v[24]) const { | 295 uint32 StrikeRegister::BestMatch(const uint8 v[24]) const { |
292 if (internal_node_head_ == kNil) { | 296 if (internal_node_head_ == kNil) { |
293 return kNil; | 297 return kNil; |
294 } | 298 } |
(...skipping 83 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
378 void StrikeRegister::FreeExternalNode(uint32 index) { | 382 void StrikeRegister::FreeExternalNode(uint32 index) { |
379 external_node_next_ptr(index) = external_node_free_head_; | 383 external_node_next_ptr(index) = external_node_free_head_; |
380 external_node_free_head_ = index; | 384 external_node_free_head_ = index; |
381 } | 385 } |
382 | 386 |
383 void StrikeRegister::FreeInternalNode(uint32 index) { | 387 void StrikeRegister::FreeInternalNode(uint32 index) { |
384 internal_nodes_[index].SetNextPtr(internal_node_free_head_); | 388 internal_nodes_[index].SetNextPtr(internal_node_free_head_); |
385 internal_node_free_head_ = index; | 389 internal_node_free_head_ = index; |
386 } | 390 } |
387 | 391 |
388 void StrikeRegister::ValidateTree( | 392 void StrikeRegister::ValidateTree(uint32 internal_node, |
389 uint32 internal_node, | 393 int last_bit, |
390 int last_bit, | 394 const vector<pair<unsigned, bool> >& bits, |
391 const vector<pair<unsigned, bool> >& bits, | 395 const set<uint32>& free_internal_nodes, |
392 const set<uint32>& free_internal_nodes, | 396 const set<uint32>& free_external_nodes, |
393 const set<uint32>& free_external_nodes, | 397 set<uint32>* used_internal_nodes, |
394 set<uint32>* used_internal_nodes, | 398 set<uint32>* used_external_nodes) { |
395 set<uint32>* used_external_nodes) { | |
396 CHECK_LT(internal_node, max_entries_); | 399 CHECK_LT(internal_node, max_entries_); |
397 const InternalNode* i = &internal_nodes_[internal_node]; | 400 const InternalNode* i = &internal_nodes_[internal_node]; |
398 unsigned bit = 0; | 401 unsigned bit = 0; |
399 switch (i->otherbits()) { | 402 switch (i->otherbits()) { |
400 case 0xff & ~(1 << 7): | 403 case 0xff & ~(1 << 7) : |
401 bit = 0; | 404 bit = 0; |
402 break; | 405 break; |
403 case 0xff & ~(1 << 6): | 406 case 0xff & ~(1 << 6) : |
404 bit = 1; | 407 bit = 1; |
405 break; | 408 break; |
406 case 0xff & ~(1 << 5): | 409 case 0xff & ~(1 << 5) : |
407 bit = 2; | 410 bit = 2; |
408 break; | 411 break; |
409 case 0xff & ~(1 << 4): | 412 case 0xff & ~(1 << 4) : |
410 bit = 3; | 413 bit = 3; |
411 break; | 414 break; |
412 case 0xff & ~(1 << 3): | 415 case 0xff & ~(1 << 3) : |
413 bit = 4; | 416 bit = 4; |
414 break; | 417 break; |
415 case 0xff & ~(1 << 2): | 418 case 0xff & ~(1 << 2) : |
416 bit = 5; | 419 bit = 5; |
417 break; | 420 break; |
418 case 0xff & ~(1 << 1): | 421 case 0xff & ~(1 << 1) : |
419 bit = 6; | 422 bit = 6; |
420 break; | 423 break; |
421 case 0xff & ~1: | 424 case 0xff & ~1: |
422 bit = 7; | 425 bit = 7; |
423 break; | 426 break; |
424 default: | 427 default: |
425 CHECK(false); | 428 CHECK(false); |
426 } | 429 } |
427 | 430 |
428 bit += 8 * i->critbyte(); | 431 bit += 8 * i->critbyte(); |
429 if (last_bit > -1) { | 432 if (last_bit > -1) { |
430 CHECK_GT(bit, static_cast<unsigned>(last_bit)); | 433 CHECK_GT(bit, static_cast<unsigned>(last_bit)); |
431 } | 434 } |
432 | 435 |
433 CHECK_EQ(free_internal_nodes.count(internal_node), 0u); | 436 CHECK_EQ(free_internal_nodes.count(internal_node), 0u); |
434 | 437 |
435 for (unsigned child = 0; child < 2; child++) { | 438 for (unsigned child = 0; child < 2; child++) { |
436 if (i->child(child) & kExternalFlag) { | 439 if (i->child(child) & kExternalFlag) { |
437 uint32 ext = i->child(child) & ~kExternalFlag; | 440 uint32 ext = i->child(child) & ~kExternalFlag; |
438 CHECK_EQ(free_external_nodes.count(ext), 0u); | 441 CHECK_EQ(free_external_nodes.count(ext), 0u); |
439 CHECK_EQ(used_external_nodes->count(ext), 0u); | 442 CHECK_EQ(used_external_nodes->count(ext), 0u); |
440 used_external_nodes->insert(ext); | 443 used_external_nodes->insert(ext); |
441 const uint8* bytes = external_node(ext); | 444 const uint8* bytes = external_node(ext); |
442 for (vector<pair<unsigned, bool> >::const_iterator i = bits.begin(); | 445 for (vector<pair<unsigned, bool> >::const_iterator i = bits.begin(); |
443 i != bits.end(); i++) { | 446 i != bits.end(); |
| 447 i++) { |
444 unsigned byte = i->first / 8; | 448 unsigned byte = i->first / 8; |
445 DCHECK_LE(byte, 0xffu); | 449 DCHECK_LE(byte, 0xffu); |
446 unsigned bit = i->first % 8; | 450 unsigned bit = i->first % 8; |
447 static const uint8 kMasks[8] = | 451 static const uint8 kMasks[8] = {0x80, 0x40, 0x20, 0x10, |
448 {0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01}; | 452 0x08, 0x04, 0x02, 0x01}; |
449 CHECK_EQ((bytes[byte] & kMasks[bit]) != 0, i->second); | 453 CHECK_EQ((bytes[byte] & kMasks[bit]) != 0, i->second); |
450 } | 454 } |
451 } else { | 455 } else { |
452 uint32 inter = i->child(child); | 456 uint32 inter = i->child(child); |
453 vector<pair<unsigned, bool> > new_bits(bits); | 457 vector<pair<unsigned, bool> > new_bits(bits); |
454 new_bits.push_back(pair<unsigned, bool>(bit, child != 0)); | 458 new_bits.push_back(pair<unsigned, bool>(bit, child != 0)); |
455 CHECK_EQ(free_internal_nodes.count(inter), 0u); | 459 CHECK_EQ(free_internal_nodes.count(inter), 0u); |
456 CHECK_EQ(used_internal_nodes->count(inter), 0u); | 460 CHECK_EQ(used_internal_nodes->count(inter), 0u); |
457 used_internal_nodes->insert(inter); | 461 used_internal_nodes->insert(inter); |
458 ValidateTree(inter, bit, bits, free_internal_nodes, free_external_nodes, | 462 ValidateTree(inter, |
459 used_internal_nodes, used_external_nodes); | 463 bit, |
| 464 bits, |
| 465 free_internal_nodes, |
| 466 free_external_nodes, |
| 467 used_internal_nodes, |
| 468 used_external_nodes); |
460 } | 469 } |
461 } | 470 } |
462 } | 471 } |
463 | 472 |
464 } // namespace net | 473 } // namespace net |
OLD | NEW |