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  )

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:

• /home/sftnight/jenkins/workspace/CvmfsDoxygen/label/docker-x86_64/cvmfs/cvmfs/ingestion/chunk_detector.h
• /home/sftnight/jenkins/workspace/CvmfsDoxygen/label/docker-x86_64/cvmfs/cvmfs/ingestion/chunk_detector.cc