CernVM-FS  2.9.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
Xor32Detector Class Reference

#include <chunk_detector.h>

Inheritance diagram for Xor32Detector:
Collaboration diagram for Xor32Detector:

Public Member Functions

 Xor32Detector (const uint64_t minimal_chunk_size, const uint64_t average_chunk_size, const uint64_t maximal_chunk_size)
 
bool MightFindChunks (const uint64_t size) const
 
- Public Member Functions inherited from ChunkDetector
 ChunkDetector ()
 
virtual ~ChunkDetector ()
 
uint64_t FindNextCutMark (BlockItem *block)
 

Protected Member Functions

virtual uint64_t DoFindNextCutMark (BlockItem *buffer)
 
virtual uint64_t DoCut (const uint64_t offset)
 
virtual uint64_t NoCut (const uint64_t offset)
 
void xor32 (const unsigned char byte)
 
bool CheckThreshold ()
 
- Protected Member Functions inherited from ChunkDetector
uint64_t last_cut () const
 
uint64_t offset () const
 

Private Member Functions

 FRIEND_TEST (T_ChunkDetectors, Xor32)
 

Private Attributes

const uint64_t minimal_chunk_size_
 
const uint64_t average_chunk_size_
 
const uint64_t maximal_chunk_size_
 
const int32_t threshold_
 
uint64_t xor32_ptr_
 
uint32_t xor32_
 

Static Private Attributes

static const unsigned kXor32Window = 32
 
static const int32_t kMagicNumber
 

Detailed Description

The xor32 rolling used in Igor-FS [1].

It takes a byte stream and constantly computes a 32-bit checksum in a way that the result is only dependent on the last read 32 bytes of the stream. Given random input data, the checksum eventually produces each number in the 32-bit value range with roughly the same probability. We exploit that by constantly checking the rolling checksum result for a specific interval. Thus, we detect characteristic 32-byte long patches in a file that do not depend on their actual position inside the data stream. Thereby local modifications of a file might not affect global chunk creation.

[1] "The Decentralized File System Igor-FS as an Application for Overlay-Networks" Dissertation of Dipl.-Ing. Kendy Kutzner (2008)

Definition at line 90 of file chunk_detector.h.

Constructor & Destructor Documentation

Xor32Detector::Xor32Detector ( const uint64_t  minimal_chunk_size,
const uint64_t  average_chunk_size,
const uint64_t  maximal_chunk_size 
)

Definition at line 52 of file chunk_detector.cc.

Here is the call graph for this function:

Member Function Documentation

bool Xor32Detector::CheckThreshold ( )
inlineprotected

Definition at line 120 of file chunk_detector.h.

Referenced by DoFindNextCutMark().

Here is the caller graph for this function:

virtual uint64_t Xor32Detector::DoCut ( const uint64_t  offset)
inlineprotectedvirtual

When returning from an implemented FindNextCutMark call you must call this function when a cut mark has been found. Like: return DoCut(found_offset)

Reimplemented from ChunkDetector.

Definition at line 105 of file chunk_detector.h.

Referenced by DoFindNextCutMark().

Here is the call graph for this function:

Here is the caller graph for this function:

uint64_t Xor32Detector::DoFindNextCutMark ( BlockItem buffer)
protectedvirtual

Implements ChunkDetector.

Definition at line 73 of file chunk_detector.cc.

Here is the call graph for this function:

Xor32Detector::FRIEND_TEST ( T_ChunkDetectors  ,
Xor32   
)
private
bool Xor32Detector::MightFindChunks ( const uint64_t  size) const
inlinevirtual

Implements ChunkDetector.

Definition at line 98 of file chunk_detector.h.

Referenced by TaskRead::Process().

Here is the caller graph for this function:

virtual uint64_t Xor32Detector::NoCut ( const uint64_t  offset)
inlineprotectedvirtual

Same as DoCut() but if no cut mark has been found in the given buffer in FindNextCutMark()

Reimplemented from ChunkDetector.

Definition at line 111 of file chunk_detector.h.

Referenced by DoFindNextCutMark().

Here is the call graph for this function:

Here is the caller graph for this function:

void Xor32Detector::xor32 ( const unsigned char  byte)
inlineprotected

Definition at line 116 of file chunk_detector.h.

Referenced by DoFindNextCutMark().

Here is the caller graph for this function:

Member Data Documentation

const uint64_t Xor32Detector::average_chunk_size_
private

Definition at line 130 of file chunk_detector.h.

Referenced by Xor32Detector().

const int32_t Xor32Detector::kMagicNumber
staticprivate
Initial value:
=
std::numeric_limits<uint32_t>::max() / 2

Definition at line 127 of file chunk_detector.h.

Referenced by CheckThreshold().

const unsigned Xor32Detector::kXor32Window = 32
staticprivate

Definition at line 126 of file chunk_detector.h.

Referenced by DoFindNextCutMark(), and Xor32Detector().

const uint64_t Xor32Detector::maximal_chunk_size_
private

Definition at line 131 of file chunk_detector.h.

Referenced by DoFindNextCutMark(), and Xor32Detector().

const uint64_t Xor32Detector::minimal_chunk_size_
private

Definition at line 129 of file chunk_detector.h.

Referenced by DoFindNextCutMark(), MightFindChunks(), and Xor32Detector().

const int32_t Xor32Detector::threshold_
private

Definition at line 132 of file chunk_detector.h.

Referenced by CheckThreshold().

uint32_t Xor32Detector::xor32_
private

Definition at line 135 of file chunk_detector.h.

Referenced by CheckThreshold(), DoCut(), and xor32().

uint64_t Xor32Detector::xor32_ptr_
private

Definition at line 134 of file chunk_detector.h.

Referenced by DoCut(), DoFindNextCutMark(), and NoCut().


The documentation for this class was generated from the following files: