From: "David Laight" <David.Laight@ACULAB.COM>
To: Antonio Quartulli <antonio@meshcoding.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 17:19:44 +0100 [thread overview]
Message-ID: <AE90C24D6B3A694183C094C60CF0A2F6026B7386@saturn3.aculab.com> (raw)
In-Reply-To: <20131009161028.GI3544@neomailbox.net>
> 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.
>
...
>
> Assuming what I said above (that we cannot make assumptions on the order of the
> entries), what is your suggestion?
I'm not sure what you are using this CRC for.
If you are trying to use it to check that the two tables match - so a
full update isn't needed then it just won't work.
If you take out 11:22:33:44:55:60 and 11:22:33:44:55:61 and
change 99:88:77:66:55:40 to 99:88:77:66:55:41 then the XOR of
the CRCs won't change.
For MAC addresses such changes aren't that unlikely.
David
next prev parent reply other threads:[~2013-10-09 16:19 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
2013-10-09 16:15 ` Antonio Quartulli
2013-10-09 16:19 ` David Laight [this message]
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=AE90C24D6B3A694183C094C60CF0A2F6026B7386@saturn3.aculab.com \
--to=david.laight@aculab.com \
--cc=antonio@meshcoding.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).