bazel-6.3.2.tar_3.gz资源-CSDN文库

101 浏览量 2024-04-05 10:21:46 上传评论收藏 75.48MB GZ 举报

共2001个文件

java：1637个

md：208个

py：56个

资源推荐

资源详情

资源评论

收起资源包目录

bazel-6.3.2.tar_3.gz （2001个子文件）

notifier.c 1KB

dummy.c 1KB

bazel.css 3KB

DS_Store 12KB

zip_headers.h 23KB

transient_bytes.h 11KB

runfiles_src.h 10KB

input_jar_scan_entries_test.h 9KB

token_stream.h 9KB

tw.h 7KB

launcher.h 6KB

combiners.h 5KB

output_jar.h 5KB

java_launcher.h 4KB

launcher_util.h 4KB

desugar_checking.h 4KB

zlib_interface.h 3KB

input_jar.h 3KB

options.h 3KB

build_info_entry_set.h 3KB

mapped_file.h 2KB

build_info_translation_helper.h 2KB

test_util.h 2KB

diag.h 2KB

port.h 2KB

data_parser.h 2KB

python_launcher.h 1KB

bash_launcher.h 1KB

command-line-reference-prefix.html 1KB

command-line-reference-suffix.html 38B

StarlarkCcCommonTest.java 331KB

StarlarkDefinedAspectsTest.java 326KB

AndroidBinaryTest.java 207KB

StarlarkRuleContextTest.java 158KB

StarlarkIntegrationTest.java 143KB

JavaStarlarkApiTest.java 140KB

StarlarkRuleImplementationFunctionsTest.java 130KB

RewindingTestsHelper.java 116KB

StarlarkAttrTransitionProviderTest.java 111KB

StarlarkRuleClassFunctionsTest.java 111KB

ModuleExtensionResolutionTest.java 109KB

SequencedSkyframeExecutorTest.java 108KB

BuildViewTestCase.java 104KB

ObjcLibraryTest.java 99KB

RemoteExecutionServiceTest.java 94KB

AndroidLibraryTest.java 92KB

CcLibraryConfiguredTargetTest.java 92KB

AbstractQueryTest.java 90KB

ObjcRuleTestCase.java 84KB

ConfigSettingTest.java 80KB

UiStateTrackerTest.java 75KB

CcBinaryThinLtoTest.java 75KB

StarlarkRuleTransitionProviderTest.java 73KB

PackageFunctionTest.java 72KB

FileFunctionTest.java 71KB

ConfigurableAttributesTest.java 69KB

StarlarkEvaluationTest.java 68KB

CcToolchainFeaturesTest.java 67KB

BuildEventStreamerTest.java 67KB

LoadingPhaseRunnerTest.java 67KB

FilesystemValueCheckerTest.java 65KB

RemoteSpawnRunnerWithGrpcRemoteExecutorTest.java 64KB

ByteStreamUploaderTest.java 63KB

FileSystemTest.java 63KB

RemoteSpawnRunnerTest.java 62KB

XcodeConfigTest.java 60KB

SelectionTest.java 59KB

ObjcStarlarkTest.java 59KB

BuildViewTest.java 58KB

ConstraintsTest.java 58KB

AspectTest.java 57KB

RecursiveFilesystemTraversalFunctionTest.java 57KB

RuleClassTest.java 54KB

DataResourceXmlTest.java 54KB

AndroidDataBindingV2Test.java 53KB

BlazeOptionHandlerTest.java 53KB

BazelJ2ObjcLibraryTest.java 53KB

CppLinkActionTest.java 52KB

ModuleFileFunctionTest.java 52KB

Desugar.java 51KB

PackageFactoryTest.java 50KB

ConvenienceSymlinkTest.java 50KB

BazelProtoLibraryTest.java 50KB

ActionCacheCheckerTest.java 50KB

StandaloneTestStrategyTest.java 49KB

ParserTest.java 48KB

AnalysisCachingTest.java 47KB

CcCommonTest.java 47KB

GrpcCacheClientTest.java 46KB

DynamicSpawnStrategyTest.java 45KB

LocalSpawnRunnerTest.java 45KB

AppleBinaryStarlarkApiTest.java 45KB

AndroidCompiledDataDeserializer.java 44KB

TreeArtifactBuildTest.java 44KB

UploadManifestTest.java 44KB

BuildIntegrationTestCase.java 42KB

LoggingInterceptorTest.java 42KB

DefaultMethodClassFixer.java 42KB

BazelBuildEventServiceModuleTest.java 42KB

FilesetEntryFunctionTest.java 41KB

共 2001 条

Everything we know about CRC but afraid to

forget

Andrew Kadatch

and Bob Jenkins

Google Inc.

Microsoft Corporation

September 3, 2010

Abstract

This pap er describes a novel interleaved, parallelizeable word-by-word

CRC computation algorithm which computes N -bit CRC (N ≤ 64) on

modern Intel and AMD processors in 1.2 CPU cycles per byte, improv-

ing state of the art over word-by-word 32-bit and 64-bit CRCs (2.1 CPU

cycles/byte) and classic byte-by-byte CRC computation (6-7 CPU cy-

cles/byte). It computes 128-bit CRC in 1.7 CPU cycles/byte.

CRC implementations are heavily optimized and hard to understand.

This paper describes CRC algorithms as they evolved over time, splitting

complex optimizations into a sequence of natural improvements.

This paper also presents a collection of CRC “tricks” that we found

handy on many occassions.

Contents

1 Deﬁnition of CRC 2

2 Related work 3

3 CRC tricks and tips 4

3.1 Incremental CRC computation . . . . . . . . . . . . . . . . . . . 4

3.2 Changing initial CRC value . . . . . . . . . . . . . . . . . . . . . 4

3.3 Concatenation of CRCs . . . . . . . . . . . . . . . . . . . . . . . 5

3.4 In-place modiﬁcation of CRC-ed message . . . . . . . . . . . . . 5

3.5 Storing CRC value after the message . . . . . . . . . . . . . . . . 6

4 Eﬃcient software implementation 7

4.1 Mapping bitstreams to hardware registers . . . . . . . . . . . . . 7

4.2 Multiplication of D-normalized polynomials . . . . . . . . . . . . 7

4.3 Multiplication of unnormalized polynomial . . . . . . . . . . . . . 7

4.4 Computing powers of x . . . . . . . . . . . . . . . . . . . . . . . 8

4.5 Simpliﬁed CRC . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

4.6 Computing a CRC byte by byte . . . . . . . . . . . . . . . . . . . 9

4.7 Rolling CRC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

4.8 Reading multiple bytes at a time . . . . . . . . . . . . . . . . . . 12

4.9 Computing a CRC word by word . . . . . . . . . . . . . . . . . . 12

4.10 Processing non-overlapping blocks in parallel . . . . . . . . . . . 13

4.11 Interleaved word-by-word CRC . . . . . . . . . . . . . . . . . . . 16

4.11.1 Parallelizing CRC computation . . . . . . . . . . . . . . . 16

4.11.2 Combining individual CRCs . . . . . . . . . . . . . . . . . 18

4.11.3 Eﬃcient computation of individual CRCs . . . . . . . . . 19

5 Experimental results 22

5.1 Testing methology . . . . . . . . . . . . . . . . . . . . . . . . . . 22

5.2 Compiler comparison . . . . . . . . . . . . . . . . . . . . . . . . . 22

5.3 Choice of interleave level . . . . . . . . . . . . . . . . . . . . . . . 23

5.4 Performance of CRC algorithms . . . . . . . . . . . . . . . . . . . 23

1 Deﬁnition of CRC

Cyclic Redundancy Check (CRC) is a well-known technique that allows the

recipient of a message transmitted over a noisy channel to detect whether the

message has been corrupted.

A message M = m

. . . m

N−1

comprised of N = |M| bits (m

∈ {0, 1}) may

be viewed either as a numeric value

M =

N−1

k=0

N−1−k

or as a polynomial of a single variable of degree (N − 1)

M(x) =

N−1

k=0

N−1−k

where m

∈ GF (2) = {0, 1} and all arithmetic operations on coeﬃcients are

performed modulo 2. For example,

Addition: (x

+ x

+ x + 1) + (x

+ x + 1) = x

+ 2x

+ 2x + 2 = x

Subtraction: (x

+ x + 1) − (x

+ x) = x

− x

+ 1 = x

+ x

+ 1,

Multiplication: (x + 1)(x + 1) = x

+ 2x + 1 = x

+ 1.

For a given polynomial P (x) of degree D = deg



P (x)



, CRC



M(x), v(x)



is the reminder from division of



M(x) · x



by P (x). In practice, a more

complex formula is used:

CRC



M(x), v(x)







v(x) − u(x)



· x

|M|

+ M (x) · x

+ u(x)



mod P(x),

(1)

where polynomial P (x) of degree D and polynomial u(x) of degree less than D

are ﬁxed.

The use of the non-zero value of u(x) guarantees that the CRC of a sequence

of zeroes is diﬀerent from zero. That allows detection of insertion of zeroes in

the beginning of a message and replacement of both content of the message and

its CRC value with zeroes. Typically,

u(x) =

D−1

k=0

. (2)

The use of auxilary parameter v(x) allows incremental CRC computation as

shown in section 3.1.

2 Related work

Cyclic Redundancy Checks (CRCs) were proposed by Peterson and Brown

[PB61] in 1961. An eﬃcient table-driven software implementation which reads

and processes data byte by byte was described by Hill [Hil79] in 1979, Perez

[Per83] in 1983. The “classic” byte-by-byte CRC algorithm described in section

4.6 was published by Sarwate [Sar88] in 1988.

In 1993, Black [Bla93] published a method that reads data by words (de-

scribed in section 4.8); however, it still computes the CRC byte by byte in strong

sequential order.

In 2001, Braun and Waldvogel [BW01] brieﬂy outlined a specialized vari-

ant of a CRC that could read input data by words and process them byte by

byte – but, thanks to the use of multiple tables, diﬀerent bytes from the input

word could be processed in parallel. In 2002, Ji and Killian [JK02] provided de-

tailed description and analysis of a nearly identical scheme. Both solutions were

targeted for hardware implementation. In 2005, Kouvanis and Berry [KB05]

demonstrated clear performance beneﬁts of this scheme even when it is im-

plemented in software. A generalized version of this approach is described in

section 4.9.

Surprisingly, until [GGO

10] we have not seen prior art describing or utiliz-

ing a method of computing a CRC by processing in parallel (in an interleaved

manner to utilize multiple ALUs) multiple input streams belonging to non-

overlapping sections of input data, desribed in section 4.10.

A novel method of CRC computation that processes in parallel multiple

words belonging to overlapping sections of input data is described in section

4.11. A special case restricted to the use of 64-bit tables, 64-bit reads, and 32

or 64-bit generating polynomials was implemented by the authors in February-

March 2007 and was used by a couple of Microsoft products. In 2009, the

algorithm was generalized and these limitations were removed.

The fact that the CRC of a message followed by its CRC is a constant value

which does not depend on the message, described in section 3.5, is well known

and has been widely used in the telecommunication industry for long time.

A method of storing a carefully chosen sequence of bits after a message so

that the CRC of a message and the sequence of bits appended to the mes-

sage produces predeﬁned result, described in 3.5, was implemented in 1990 by

Zemtsov [Zem90].

A method for recomputing a known CRC using a new initial CRC value,

described in section 3.2, and the method of computing a CRC of the concatena-

tion of messages having known CRC values without touching the actual data,

described in section 3.3, were implemented by one of the authors in 2005 but

were not published.

3 CRC tricks and tips

3.1 Incremental CRC computation

The use of an arbitrary initial CRC value v(x) allows computation of a CRC

incrementally. If a message M(x) = M

(x) · x

+ M

(x) is a concatenation

of messages M

and M

, its CRC may be computed piece by piece because

CRC



M(x), v(x)



= CRC



(x), CRC



(x), v(x)





. (3)

Indeed,

CRC

(M, v) =



(v − u)x

|M|

+ M x

+ u



mod P =



(v − u)x

|+|M

+ (M

+ M

+ u



mod P =





(v − u)x

+ M



+ M

+ u



mod P =



CRC

, v)x

+ M

+ u



mod P =

= CRC



, CRC

, v)



3.2 Changing initial CRC value

If CRC



M(x), v(x)



for some initial value v(x) is known, it is possible to

compute CRC



M(x), v

(x)



for diﬀerent initial value v

(x) without touching

the value of M (x):

CRC

(M, v

) = CRC

(M, v) +



− v)x

|M|



mod P. (4)

Proof:

CRC

(M, v

) =



− u)x

|M|

+ M x

+ u



mod P =





− u) + (v − v)



|M|

+ M x

+ u



mod P =





(v − u) + (v

− v)



|M|

+ M x

+ u



mod P =





(v − u)x

|M|

+ M x

+ u



+ (v

− v)x

|M|



mod P =

= CRC

(M, v) +



− v)x

|M|

mod P



3.3 Concatenation of CRCs

If a message M(x) = M

(x) · x

+ M

(x) is a concatenation of messages

and M

, and CRCs of M

, M

(computed with some initial values v

(x),

(x) respectively) are known, CRC



M(x), v(x)



may be computed without

touching contents of the message M:

1. Using formula (4), the value of v

= CRC

, v) may be computed from

the known CRC

, v

) without touching the contents of M

2. Then, v

= CRC

, v

) may be computed from known CRC

, v

)

without touching the contents of M

According to (3), CRC

(M, v) = v

3.4 In-place modiﬁcation of CRC-ed message

Sometimes it is necessary to replace a part of message M(x) in-place and re-

compute CRC of modiﬁed message M(x) eﬃciently.

If a message M = ABC is a concatenation of messages A, B, and C, and

(x) is new message of the same length as B(x), CRC

) of message M

C may be computed from known CRC

(M). Indeed,

M(x) = A(x) · x

|B|+|C|

+ B(x) · x

|C|

+ C(x),

(x) = A(x) · x

|B|+|C|

+ B

(x) · x

|C|

+ C(x) =

= M(x) +



(x) − B(x)



· x

|C|

therefore

CRC



(x), v(x)



= CRC



M(x) +



(x) − B(x)



· x

|C|







v(x) − u(x)



|M|

+ M (x)x



(x) − B(x)



|C|+D

+ u(x)



mod P(x)



CRC



M(x), v(x)





(x) − B(x)



|C|+D



mod P(x) =

= CRC



M(x), v(x)







(x) − B(x)



|C|+D

mod P(x)



评论收藏

内容反馈

程序员Chino的日记

粉丝: 3644
资源: 5万+

bazel-6.3.2.tar_3.gz

filebeat-6.3.2-linux-x86_64.tar.gz

proj-6.3.2.tar.gz

CDH-6.3.2-1.cdh6.3.2.p0.1605554-el7.parcel.sha1

CDH-6.3.2-1.cdh6.3.2.p0.1605554-el7.parcel.sha

kibana-6.3.2-linux-x86_64.tar.gz

icepdf-pro-trial-6.3.2.tar

logstash-6.3.2.tar.gz

icepdf-pro-trial-6.3.2.zip

elasticsearch-analysis-ik-6.3.2.zip

icepdf-core-6.3.2.jar

grafana-6.3.2.linux-amd64.tar.gz

CDH-6.3.2-1.cdh6.3.2.p0.1605554-el7.parcel.zip.002

CDH-6.3.2-1.cdh6.3.2.p0.1605554-el7.parcel.zip.001

CDH-6.3.2-1.cdh6.3.2.p0.1605554-el7.parcel.zip.003

VNC-Server-6.3.2-Linux-x86-ANY.tar

elasticsearch-6.3.2.tar.gz

icepdf-pro-trial-6.3.2.zip 完整版 pdf转PNG

CDH6.3.2安装包及安装教程

cdh6.3.2安装包全套

Elasticsearch-6.3.2（Linux+Win）+中文分词ik-6.3.2.zip

CDH6.3.2安装包下载

flink-1.12-CDH-6.3.2.zip

apache-atlas-2.1.0-bin.tar.gz--基于cdh6.3.1编译完成

Linux/macOS qt-everywhere-src-6.3.2.tar.xz

oracle-j2sdk1.8-1.8.0+update181-1.x86_64_百度云资源.txt

CDH6.3.2安装包及下载地址

x-pack-core-6.3.2.jar

spark-streaming-kafka-0-10_2.11-2.4.0-cdh6.1.1.jar

LibreOffice_6.1.6_Linux_x86-64_rpm_langpack_zh-CN

最新资源