| 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 |