From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-in7.apple.com (mail-out7.apple.com [17.151.62.29]) (using TLSv1 with cipher AES256-SHA (256/256 bits)) (No client certificate requested) by ml01.01.org (Postfix) with ESMTPS id 076771A1DF3 for ; Tue, 30 Aug 2016 09:15:56 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; d=apple.com; s=mailout2048s; c=relaxed/simple; q=dns/txt; i=@apple.com; t=1472573756; x=2336487356; h=From:Sender:Reply-To:Subject:Date:Message-id:To:Cc:MIME-version:Content-type: Content-transfer-encoding:Content-ID:Content-Description:Resent-Date:Resent-From: Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID:In-reply-to:References:List-Id: List-Help:List-Unsubscribe:List-Subscribe:List-Post:List-Owner:List-Archive; bh=054YwIde5cdsiY/+sAepeO2P9otRuZyITsNxmPf/8M8=; b=rLSyEFDPQPPDbxYG5gEeWt8Wf0mJBfhYtc1ApfvEiBiYa4cm2bhwaHggAGqwPJP0 tweqqD4mstcxsJC3JJ2utXM46cZ1sYSott4Cz7oTEzkEOuUty5mpux3+wfXk4gvi hmcWJKB0KRifvK3SUAsmLe6Qb6XfDDaHjdGL80pBJn9l3ulvV03e/IBDLKDbnmml 7fIT+oAmuYSIoQjCuDGt3/TNybGurcTxb4Pm9r2QoDVdUGsiARD+LJ94nNdktkvu YA31T18zMeo93XLqkuabNb5tvUnkYYwiQWRxlIuSMsV6U9Ln6kLc1Gzoo7F0nrPm ERnSfgft3yL89hyum9ahrQ==; Received: from relay3.apple.com (relay3.apple.com [17.128.113.83]) by mail-in7.apple.com (Apple Secure Mail Relay) with SMTP id A5.ED.17422.C31B5C75; Tue, 30 Aug 2016 09:15:56 -0700 (PDT) X-AuditID: 11973e16-f793f6d00000440e-93-57c5b13caf4c Received: from nwk-mmpp-sz08.apple.com (nwk-mmpp-sz08.apple.com [17.128.115.25]) by relay3.apple.com (Apple SCV relay) with SMTP id 20.5C.18578.C31B5C75; Tue, 30 Aug 2016 09:15:56 -0700 (PDT) MIME-version: 1.0 Received: from [17.114.155.95] by nwk-mmpp-sz08.apple.com (Oracle Communications Messaging Server 8.0.1.1.0 64bit (built Jun 15 2016)) with ESMTPSA id <0OCQ00HFAD6KX800@nwk-mmpp-sz08.apple.com>; Tue, 30 Aug 2016 09:15:56 -0700 (PDT) Sender: afish@apple.com From: Andrew Fish In-reply-to: Date: Tue, 30 Aug 2016 09:15:56 -0700 Cc: edk2-devel , Michael Zimmermann Message-id: References: <91B24DF7-4F53-4DEF-A600-755A69368B79@apple.com> To: valerij zaporogeci X-Mailer: Apple Mail (2.3112) X-Brightmail-Tracker: H4sIAAAAAAAAA+NgFjrFLMWRmVeSWpSXmKPExsUi2FAYrGuz8Wi4wcs2BYs9h44yW8yd+pTV 4vG/dmYHZo+ds+6ye3TP/scSwBTFZZOSmpNZllqkb5fAlfF5+W/mgh06FTdeNbE2MPaodDFy ckgImEisXdbDCGGLSVy4t54NxBYS2MsoseO+WRcjB1jN95niXYxcQOGDjBKPPi4Aq+EVEJT4 MfkeC0gNs4C8xMHzsiBhZgEtie+PWlkg6t8xSrz+tZcFJCEsIC7x7swmZghbUuL69VnsIDab gLLEivkfwGxOgWCJbW9vsoLYLAKqEis6W1ghhkZKnGo4zQSx10biyoIT7BB33mKS6JjvDWKL COhIHLx/kRniF1mJfRtA7uQCsvewSSyd+5JtAqPILCR3z0K4exaSuxcwMq9iFMpNzMzRzcwz 10ssKMhJ1UvOz93ECAr86XZiOxgfrrI6xCjAwajEw3tg1tFwIdbEsuLK3EOM0hwsSuK8m7Yc CRcSSE8sSc1OTS1ILYovKs1JLT7EyMTBKdXAqFO5/VyG8G/fyBk8dyLvxs1MOuHw+OVSFw4G gaDi+uVzZZhtOs7oHl1f/+DID52Pq95cnGC45eRFh0C36ze399os0dwhwhLEel9KMe3QIa04 VsWJYblc+f+iLjpLX9C4t6+j4u62pc0RZqWPPB79OHFr/eqMOTw3086EZf9xqypaJnv93MHT j5VYijMSDbWYi4oTAXV0G/NdAgAA X-Brightmail-Tracker: H4sIAAAAAAAAA+NgFmpjkeLIzCtJLcpLzFFi42IRbCiW1LXZeDTcYGubhMWeQ0eZLeZOfcpq 8fhfO7MDs8fOWXfZPbpn/2MJYIrisklJzcksSy3St0vgyvi8/DdzwQ6dihuvmlgbGHtUuhg5 OCQETCS+zxTvYuQEMsUkLtxbz9bFyMUhJHCQUeLRxwVsIAleAUGJH5PvsYDUMwvISxw8LwsS ZhbQkvj+qJUFov4do8TrX3tZQBLCAuIS785sYoawJSWuX5/FDmKzCShLrJj/AczmFAiW2Pb2 JiuIzSKgKrGis4UVYmikxKmG00wQe20kriw4AVYvJHCLSaJjvjeILSKgI3Hw/kVmiKNlJfZt WMA2gVFwFpJTZyGcOgvJqQsYmVcxChSl5iRWGuslFhTkpOol5+duYgSHamHwDsY/y6wOMQpw MCrx8B6YdTRciDWxrLgy9xCjBAezkgjvwtVAId6UxMqq1KL8+KLSnNTiQ4zJQPdPZJYSTc4H xlFeSbyhiYmBibGxmbGxuYk5acJK4rw/3h8JFxJITyxJzU5NLUgtgtnCxMEp1cDoaJn9ZOn5 O3ua7to6HXr0/OmRyFtvVjZWHY532+Co9y90cubB/GnTixqPfpv9xDuiak9t7pmDbcFJ/4OP aOanLTfidFr407Z+S3uOLu/Lx6d/5EwxZ6u6c08s5+6+suCJczeb7HFK2ZozWWumR+XPCQq3 toemWWhU73zJp792Zc+R5/e2PmFJUGIpzkg01GIuKk4EAO2E0ZOZAgAA Subject: Re: Crc32 X-BeenThere: edk2-devel@lists.01.org X-Mailman-Version: 2.1.21 Precedence: list List-Id: EDK II Development List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 30 Aug 2016 16:15:57 -0000 Content-transfer-encoding: 7BIT Content-type: text/plain; CHARSET=US-ASCII > On Aug 30, 2016, at 8:17 AM, valerij zaporogeci wrote: > > well, that bit in the 32th (bit 33) term of the polynomial is > "implied", but it should be used, otherwise it would not give a 32 bit > remainder (crc). if to count 04c11db7 as a polynomial, its non-zero > msbit is bit 26, so with it, it would be crc25. > Why results don't match, I suspect it's becuase that pre- and post- > processing involved. Tianocore algorithm inverses bits at the > beginning and in the end. > Pure definition of CRC doesn't require this. It would be good to know > the exact specification on the algorithm and its nuances. > And of course in the pure case, calculating CRC on the polynomial > itself should give 0 (since polynomial itself is multiple of itself). > It's the easiest way to check. So CRC of 104c11db7 = 0 > In the the above calculator (in the Michael's response), neither > CRC(104c11db7) nor CRC(04c11db7) gives 0. (4E24FFBE and B79B7E7A > respectively). > So if it is a right CRC32, then it's not a pure CRC mathematically. > and additionally processed. How? and where it is possible to learn > that? > I don't know the math here as well as you do so I will not comment on that. My guess is this is an old algorithm that was optimized for 32-bit hardware. 64-bit math would require a lot software math libraries and it would be much slower than doing 32-bit math on a processors ALU. If you want to research the history of this algorithm your best bet it to research the CRC32 used in old school Ethernet. The CRC got added to the (U)EFI spec about 17 years ago and it was probably copying something that was 25-30 years old, but that is just my best guess as Ken called in rich a long time ago and does not work on things EFI at this point. Thanks, Andrew Fish > > 2016-08-30 17:09 GMT+03:00, Andrew Fish : >> >>> On Aug 30, 2016, at 6:32 AM, valerij zaporogeci >>> wrote: >>> >>> Thank you. >>> But the polynomial value for CCITT crc32 is 104c11db7, not its tail >>> 04c11db7. >> >> The spec does not say it is a CCITT, it states it uses the CCITT algorithm >> with a seed polynomial of 0x04c11db7. >> >> >>> And this whole mess with all those online calculators was the exact >>> reson I asked here. Because they mostly give WRONG result. As your >>> example. It's easy to check it's wrong. Because for example leading >>> zeroes in the message MUST not change the Crc32. >>> Here we have: >>> for 01 -> CD39D477 >>> for 00 01 -> D71E16AC >>> and so on. >>> Also, it's obvious that Crc32(1) would be a polynomial without the >>> most significant non-zero bit, thus crc32 from 1 by the polynomial >>> 104c11db7 would be 04c11b7. >>> The only online calculator so far giving right results is here: >>> https://ghsi.de/CRC/index.php?Polynom=100000100110000010001110110110111&Message=0104c11db7 >>> >>> I wrote function following the mathematics of the Crc and it gives >>> results exactly like in the above calculator. >>> It's fun to imagine what happens with such an incompatibilty for >>> example in case of GPT header. >>> >> >> As far as I can tell this is used in a lot of real world things: HDLC, ANSI >> X3.66, ITU-T V.42, Ethernet, Serial ATA, MPEG-2, PKZIP, Gzip, Bzip2, >> PNG,[36] many others[1] >> >> I think Ken added this to the spec in the last millennium. Ken's background >> was networking and Windows X86 HAL so I'm assuming he picked the same CRC as >> Ethernet? >> >> It is always possible we could have botched the math some place along the >> way and not noticed as we are self consistent so everything appears to >> work. >> >> Thanks, >> >> Andrew Fish >> >> [1] https://en.wikipedia.org/wiki/Cyclic_redundancy_check >> >> >>> 2016-08-30 14:08 GMT+03:00, Michael Zimmermann >>> : >>>> well as u already said, the spec says it uses 'a standard CCITT32 CRC >>>> algorithm with a seed polynomial value of 0x04c11db7' >>>> >>>> this is the implementation which confirms it: >>>> https://github.com/tianocore/edk2/blob/master/MdeModulePkg/Core/RuntimeDxe/Crc32.c >>>> >>>> after testing it it indeed produces CCITT32 results like this online >>>> generator: >>>> http://g6auc.me.uk/CRC32/index.html >>>> >>>> Thanks >>>> Michael >>>> >>>> On Tue, Aug 30, 2016 at 2:54 AM, valerij zaporogeci >>>> >>>> wrote: >>>> >>>>> Hi, all. >>>>> Yet another dumb question from me. >>>>> UEFI specification has Crc32 calculation service and uses Crc32 in >>>>> several places. but it only humbly mentions in the note somewhere in >>>>> the description of System Table about what exact one it wants. Namely >>>>> it states that the polynomial seed is 04c11db7. And that's all. >>>>> My question is - does really the specification means the 33-bit >>>>> polynomial >>>>> 104c11db7? And is the algorithm just a plain remainder calculation >>>>> without any additional pre/post processing of it? So that for example >>>>> Crc32 of the 4-byte sequence b16b00b5 would be >>>>> 8c1f0a7c? >>>>> Thank you. >>>>> _______________________________________________ >>>>> edk2-devel mailing list >>>>> edk2-devel@lists.01.org >>>>> https://lists.01.org/mailman/listinfo/edk2-devel >>>>> >>>> >>> _______________________________________________ >>> edk2-devel mailing list >>> edk2-devel@lists.01.org >>> https://lists.01.org/mailman/listinfo/edk2-devel >> >> > _______________________________________________ > edk2-devel mailing list > edk2-devel@lists.01.org > https://lists.01.org/mailman/listinfo/edk2-devel