From: Antonio Quartulli <antonio@meshcoding.com>
To: David Laight <David.Laight@ACULAB.COM>
Cc: netdev@vger.kernel.org, b.a.t.m.a.n@lists.open-mesh.org,
Marek Lindner <lindner_marek@yahoo.de>,
davem@davemloft.net, Antonio Quartulli <ordex@autistici.org>
Subject: Re: [B.A.T.M.A.N.] [PATCH 10/16] batman-adv: use CRC32C instead of CRC16 in TT code
Date: Wed, 9 Oct 2013 18:10:28 +0200 [thread overview]
Message-ID: <20131009161028.GI3544@neomailbox.net> (raw)
In-Reply-To: <AE90C24D6B3A694183C094C60CF0A2F6026B7385@saturn3.aculab.com>
[-- Attachment #1: Type: text/plain, Size: 1358 bytes --]
On Wed, Oct 09, 2013 at 04:49:53PM +0100, David Laight wrote:
> > > Are you really generating CRC32 of a pile of ethernet MAC addresses
> > > and the XORing the CRC together?
> > > That gives the same answer as XORing together the MAC addresses and
> > > then doing a CRC of the final value.
> >
> > I was not sure about this since the CRC32 is not a linear operation. However
> > this routine is not on the fast path, so we can also live with this order.
>
> All CRC are linear.
> Because '(a + b) mod c' is the same as '((a mod c) + (b mod c)) mod c'.
>
> The CRC of a buffer is the XOR of the CRCs generated for each '1' bit.
> The CRC for each bit depends on how far it is from the end of the buffer.
In our tables we cannot make any assumption about the order of the entries: the
node whom generated the table may store the entries in a different order from
what we have got.
This is why I did not implemented it as a simple CRC of the
whole the GlobalTable/buffer but I CRC'd each MAC+VID on its own.
> Presetting the CRC to all-ones generates a value that is dependent on
> the length of the buffer - otherwise missing/extra leading zeros are
> not detected.
Assuming what I said above (that we cannot make assumptions on the order of the
entries), what is your suggestion?
Regards,
--
Antonio Quartulli
[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 836 bytes --]
next prev parent reply other threads:[~2013-10-09 16:10 UTC|newest]
Thread overview: 28+ messages / expand[flat|nested] mbox.gz Atom feed top
2013-10-09 12:40 [B.A.T.M.A.N.] pull request: batman-adv 2013-10-09 Antonio Quartulli
2013-10-09 12:40 ` [B.A.T.M.A.N.] [PATCH 01/16] MAINTAINERS: batman-adv - update emails Antonio Quartulli
2013-10-09 12:40 ` [B.A.T.M.A.N.] [PATCH 02/16] batman-adv: switch to a new packet compatibility version Antonio Quartulli
2013-10-09 12:40 ` [B.A.T.M.A.N.] [PATCH 03/16] batman-adv: tvlv - basic infrastructure Antonio Quartulli
2013-10-09 12:40 ` [B.A.T.M.A.N.] [PATCH 04/16] batman-adv: tvlv - gateway download/upload bandwidth container Antonio Quartulli
2013-10-09 12:40 ` [B.A.T.M.A.N.] [PATCH 05/16] batman-adv: tvlv - add distributed arp table container Antonio Quartulli
2013-10-09 12:40 ` [B.A.T.M.A.N.] [PATCH 06/16] batman-adv: tvlv - add network coding container Antonio Quartulli
2013-10-09 12:40 ` [B.A.T.M.A.N.] [PATCH 07/16] batman-adv: tvlv - convert tt data sent within OGMs Antonio Quartulli
2013-10-09 12:40 ` [B.A.T.M.A.N.] [PATCH 08/16] batman-adv: tvlv - convert tt query packet to use tvlv unicast packets Antonio Quartulli
2013-10-09 12:40 ` [B.A.T.M.A.N.] [PATCH 09/16] batman-adv: tvlv - convert roaming adv " Antonio Quartulli
2013-10-09 12:40 ` [B.A.T.M.A.N.] [PATCH 10/16] batman-adv: use CRC32C instead of CRC16 in TT code Antonio Quartulli
2013-10-09 14:11 ` David Laight
2013-10-09 14:35 ` Antonio Quartulli
2013-10-09 15:49 ` David Laight
2013-10-09 16:10 ` Antonio Quartulli [this message]
2013-10-09 16:15 ` Antonio Quartulli
2013-10-09 16:19 ` David Laight
2013-10-09 17:05 ` Antonio Quartulli
2013-10-09 12:40 ` [B.A.T.M.A.N.] [PATCH 11/16] batman-adv: move BATADV_TT_CLIENT_TEMP to higher bit Antonio Quartulli
2013-10-09 12:40 ` [B.A.T.M.A.N.] [PATCH 12/16] batman-adv: remove vis functionality Antonio Quartulli
2013-10-09 12:40 ` [B.A.T.M.A.N.] [PATCH 13/16] batman-adv: add build check macros for packet member offset Antonio Quartulli
2013-10-09 12:40 ` [B.A.T.M.A.N.] [PATCH 14/16] batman-adv: reorder packet types Antonio Quartulli
2013-10-09 12:40 ` [B.A.T.M.A.N.] [PATCH 15/16] batman-adv: remove packed from batadv_ogm_packet Antonio Quartulli
2013-10-09 12:40 ` [B.A.T.M.A.N.] [PATCH 16/16] batman-adv: reorder batadv_iv_flags Antonio Quartulli
2013-10-09 17:56 ` [B.A.T.M.A.N.] pull request: batman-adv 2013-10-09 David Miller
2013-10-09 18:53 ` David Miller
2013-10-09 19:01 ` Antonio Quartulli
2013-10-09 19:32 [B.A.T.M.A.N.] pull request: batman-adv 2013-10-09b Antonio Quartulli
2013-10-09 19:32 ` [B.A.T.M.A.N.] [PATCH 10/16] batman-adv: use CRC32C instead of CRC16 in TT code Antonio Quartulli
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20131009161028.GI3544@neomailbox.net \
--to=antonio@meshcoding.com \
--cc=David.Laight@ACULAB.COM \
--cc=b.a.t.m.a.n@lists.open-mesh.org \
--cc=davem@davemloft.net \
--cc=lindner_marek@yahoo.de \
--cc=netdev@vger.kernel.org \
--cc=ordex@autistici.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).