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 <limits> | 7 #include <limits> |
8 | 8 |
9 #include "base/logging.h" | 9 #include "base/logging.h" |
10 | 10 |
(...skipping 97 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
108 external_nodes_.reset(new uint8[kExternalNodeSize * max_entries]); | 108 external_nodes_.reset(new uint8[kExternalNodeSize * max_entries]); |
109 | 109 |
110 Reset(); | 110 Reset(); |
111 } | 111 } |
112 | 112 |
113 StrikeRegister::~StrikeRegister() { delete[] internal_nodes_; } | 113 StrikeRegister::~StrikeRegister() { delete[] internal_nodes_; } |
114 | 114 |
115 void StrikeRegister::Reset() { | 115 void StrikeRegister::Reset() { |
116 // Thread a free list through all of the internal nodes. | 116 // Thread a free list through all of the internal nodes. |
117 internal_node_free_head_ = 0; | 117 internal_node_free_head_ = 0; |
118 for (unsigned i = 0; i < max_entries_ - 1; i++) | 118 for (unsigned i = 0; i < max_entries_ - 1; i++) { |
119 internal_nodes_[i].SetNextPtr(i + 1); | 119 internal_nodes_[i].SetNextPtr(i + 1); |
| 120 } |
120 internal_nodes_[max_entries_ - 1].SetNextPtr(kNil); | 121 internal_nodes_[max_entries_ - 1].SetNextPtr(kNil); |
121 | 122 |
122 // Also thread a free list through the external nodes. | 123 // Also thread a free list through the external nodes. |
123 external_node_free_head_ = 0; | 124 external_node_free_head_ = 0; |
124 for (unsigned i = 0; i < max_entries_ - 1; i++) | 125 for (unsigned i = 0; i < max_entries_ - 1; i++) { |
125 external_node_next_ptr(i) = i + 1; | 126 external_node_next_ptr(i) = i + 1; |
| 127 } |
126 external_node_next_ptr(max_entries_ - 1) = kNil; | 128 external_node_next_ptr(max_entries_ - 1) = kNil; |
127 | 129 |
128 // This is the root of the tree. | 130 // This is the root of the tree. |
129 internal_node_head_ = kNil; | 131 internal_node_head_ = kNil; |
130 } | 132 } |
131 | 133 |
132 InsertStatus StrikeRegister::Insert(const uint8 nonce[32], | 134 InsertStatus StrikeRegister::Insert(const uint8 nonce[32], |
133 uint32 current_time_external) { | 135 uint32 current_time_external) { |
134 // Make space for the insertion if the strike register is full. | 136 // Make space for the insertion if the strike register is full. |
135 while (external_node_free_head_ == kNil || | 137 while (external_node_free_head_ == kNil || |
(...skipping 161 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
297 CHECK_LT(i, max_entries_); | 299 CHECK_LT(i, max_entries_); |
298 CHECK_EQ(free_external_nodes.count(i), 0u); | 300 CHECK_EQ(free_external_nodes.count(i), 0u); |
299 free_external_nodes.insert(i); | 301 free_external_nodes.insert(i); |
300 } | 302 } |
301 | 303 |
302 set<uint32> used_external_nodes; | 304 set<uint32> used_external_nodes; |
303 set<uint32> used_internal_nodes; | 305 set<uint32> used_internal_nodes; |
304 | 306 |
305 if (internal_node_head_ != kNil && | 307 if (internal_node_head_ != kNil && |
306 ((internal_node_head_ >> 8) & kExternalFlag) == 0) { | 308 ((internal_node_head_ >> 8) & kExternalFlag) == 0) { |
307 vector<pair<unsigned, bool> > bits; | 309 vector<pair<unsigned, bool>> bits; |
308 ValidateTree(internal_node_head_ >> 8, -1, bits, free_internal_nodes, | 310 ValidateTree(internal_node_head_ >> 8, -1, bits, free_internal_nodes, |
309 free_external_nodes, &used_internal_nodes, | 311 free_external_nodes, &used_internal_nodes, |
310 &used_external_nodes); | 312 &used_external_nodes); |
311 } | 313 } |
312 } | 314 } |
313 | 315 |
314 // static | 316 // static |
315 uint32 StrikeRegister::TimeFromBytes(const uint8 d[4]) { | 317 uint32 StrikeRegister::TimeFromBytes(const uint8 d[4]) { |
316 return static_cast<uint32>(d[0]) << 24 | | 318 return static_cast<uint32>(d[0]) << 24 | |
317 static_cast<uint32>(d[1]) << 16 | | 319 static_cast<uint32>(d[1]) << 16 | |
(...skipping 116 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
434 void StrikeRegister::FreeExternalNode(uint32 index) { | 436 void StrikeRegister::FreeExternalNode(uint32 index) { |
435 external_node_next_ptr(index) = external_node_free_head_; | 437 external_node_next_ptr(index) = external_node_free_head_; |
436 external_node_free_head_ = index; | 438 external_node_free_head_ = index; |
437 } | 439 } |
438 | 440 |
439 void StrikeRegister::FreeInternalNode(uint32 index) { | 441 void StrikeRegister::FreeInternalNode(uint32 index) { |
440 internal_nodes_[index].SetNextPtr(internal_node_free_head_); | 442 internal_nodes_[index].SetNextPtr(internal_node_free_head_); |
441 internal_node_free_head_ = index; | 443 internal_node_free_head_ = index; |
442 } | 444 } |
443 | 445 |
444 void StrikeRegister::ValidateTree( | 446 void StrikeRegister::ValidateTree(uint32 internal_node, |
445 uint32 internal_node, | 447 int last_bit, |
446 int last_bit, | 448 const vector<pair<unsigned, bool>>& bits, |
447 const vector<pair<unsigned, bool> >& bits, | 449 const set<uint32>& free_internal_nodes, |
448 const set<uint32>& free_internal_nodes, | 450 const set<uint32>& free_external_nodes, |
449 const set<uint32>& free_external_nodes, | 451 set<uint32>* used_internal_nodes, |
450 set<uint32>* used_internal_nodes, | 452 set<uint32>* used_external_nodes) { |
451 set<uint32>* used_external_nodes) { | |
452 CHECK_LT(internal_node, max_entries_); | 453 CHECK_LT(internal_node, max_entries_); |
453 const InternalNode* i = &internal_nodes_[internal_node]; | 454 const InternalNode* i = &internal_nodes_[internal_node]; |
454 unsigned bit = 0; | 455 unsigned bit = 0; |
455 switch (i->otherbits()) { | 456 switch (i->otherbits()) { |
456 case 0xff & ~(1 << 7): | 457 case 0xff & ~(1 << 7): |
457 bit = 0; | 458 bit = 0; |
458 break; | 459 break; |
459 case 0xff & ~(1 << 6): | 460 case 0xff & ~(1 << 6): |
460 bit = 1; | 461 bit = 1; |
461 break; | 462 break; |
(...skipping 36 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
498 for (const pair<unsigned, bool>& pair : bits) { | 499 for (const pair<unsigned, bool>& pair : bits) { |
499 unsigned byte = pair.first / 8; | 500 unsigned byte = pair.first / 8; |
500 DCHECK_LE(byte, 0xffu); | 501 DCHECK_LE(byte, 0xffu); |
501 unsigned bit_new = pair.first % 8; | 502 unsigned bit_new = pair.first % 8; |
502 static const uint8 kMasks[8] = | 503 static const uint8 kMasks[8] = |
503 {0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01}; | 504 {0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01}; |
504 CHECK_EQ((bytes[byte] & kMasks[bit_new]) != 0, pair.second); | 505 CHECK_EQ((bytes[byte] & kMasks[bit_new]) != 0, pair.second); |
505 } | 506 } |
506 } else { | 507 } else { |
507 uint32 inter = i->child(child); | 508 uint32 inter = i->child(child); |
508 vector<pair<unsigned, bool> > new_bits(bits); | 509 vector<pair<unsigned, bool>> new_bits(bits); |
509 new_bits.push_back(pair<unsigned, bool>(bit, child != 0)); | 510 new_bits.push_back(pair<unsigned, bool>(bit, child != 0)); |
510 CHECK_EQ(free_internal_nodes.count(inter), 0u); | 511 CHECK_EQ(free_internal_nodes.count(inter), 0u); |
511 CHECK_EQ(used_internal_nodes->count(inter), 0u); | 512 CHECK_EQ(used_internal_nodes->count(inter), 0u); |
512 used_internal_nodes->insert(inter); | 513 used_internal_nodes->insert(inter); |
513 ValidateTree(inter, bit, bits, free_internal_nodes, free_external_nodes, | 514 ValidateTree(inter, bit, bits, free_internal_nodes, free_external_nodes, |
514 used_internal_nodes, used_external_nodes); | 515 used_internal_nodes, used_external_nodes); |
515 } | 516 } |
516 } | 517 } |
517 } | 518 } |
518 | 519 |
519 } // namespace net | 520 } // namespace net |
OLD | NEW |