From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-lf0-x22b.google.com (mail-lf0-x22b.google.com [IPv6:2a00:1450:4010:c07::22b]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by lists.bufferbloat.net (Postfix) with ESMTPS id 423FF3B2A4 for ; Sun, 26 Mar 2017 12:16:18 -0400 (EDT) Received: by mail-lf0-x22b.google.com with SMTP id x137so10892745lff.3 for ; Sun, 26 Mar 2017 09:16:18 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:subject:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to; bh=J5n14BGfoJ8Z3602gKQax4xuarDdo2wm6kCPCBvA7Io=; b=rLrN3MCDu4uNdW6X20nmiPn5RiTypm+nxtzsTlkeZ/yOyC7isokS3gLmixqTulms4k aRv7eE220hQZVku7BrquHTYYT8n0AbUnOxnFN/uEhudEiwndeWZPxkvsXEdzuf35oCFT /3eeY3ti7OFkRx6ZyJAZZZUlwzEYqQWYoSLp4n9SpD80f502G7sUacqFQBVVtAzr0oPu KS3BJZ4Gznh3+bYtFhl3V9g2M00Fj2NnYes8GExdJ0lhDyhm3AabCORIhK3tpO9OyKNK jh5bSsJo6I/SwFwiUOVlL36T0FTexHg9zJsYyYQ3GKFrgnlp7U/uTXs6wVvWfarjkE5+ ZemQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:subject:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to; bh=J5n14BGfoJ8Z3602gKQax4xuarDdo2wm6kCPCBvA7Io=; b=R0j+nuQ/oZZl8dUI9Stw7UMWFNdnDoz7eiHBaOoMcxS8mo20QG6lWlHLmyO7tdqmSi CN6kRb5kI18FBXhXqLycIJpQS4SMncLUy4tD+7tlJAxPRBKQ03CvetPYwGOkSLGOGvBS F/xzwNsHpZxP5EO2xP+6pdrACMuIVecmLm6dNO0KK8QqLx8dTlH9+LSZeixGAvZYCjea +7knJDn5bLPWURCHdfpyA9ofFjH72r6W8MD0eFsnibEtbvbEmImUF1eiLd4E+VXLxIYa Rsyym2L6C5NuMX2JwtTyZ7/4PBzrqHsxtDdZZM7tFnSF+jvG+y8wRyrtIuuIlTVQ/gm4 6mkg== X-Gm-Message-State: AFeK/H2YZsV9/mhK4rxGgAoLpeeAiwh4Vo4QV9UJKw5pUQdlOU6IttFauJXt39LCE89VsA== X-Received: by 10.25.43.8 with SMTP id r8mr7728604lfr.41.1490544976770; Sun, 26 Mar 2017 09:16:16 -0700 (PDT) Received: from [192.168.100.14] (37-219-158-10.nat.bb.dnainternet.fi. [37.219.158.10]) by smtp.gmail.com with ESMTPSA id i1sm1503863ljd.47.2017.03.26.09.16.15 (version=TLS1 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Sun, 26 Mar 2017 09:16:16 -0700 (PDT) Content-Type: text/plain; charset=utf-8 Mime-Version: 1.0 (Mac OS X Mail 9.3 \(3124\)) From: Jonathan Morton In-Reply-To: Date: Sun, 26 Mar 2017 19:16:13 +0300 Cc: Cake List Content-Transfer-Encoding: quoted-printable Message-Id: References: To: Dave Taht X-Mailer: Apple Mail (2.3124) Subject: Re: [Cake] an experiment with an alternate hasher X-BeenThere: cake@lists.bufferbloat.net X-Mailman-Version: 2.1.20 Precedence: list List-Id: Cake - FQ_codel the next generation List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 26 Mar 2017 16:16:18 -0000 > On 26 Mar, 2017, at 19:00, Dave Taht wrote: >=20 > popcount is, regrettably, an sse4.2-only instruction A read through the ARM ISA Quick Reference Card: = http://infocenter.arm.com/help/topic/com.arm.doc.qrc0001m/QRC0001_UAL.pdf =E2=80=A6shows that there is no equivalent instruction on ARM CPUs at = least up to ARMv7, which I think covers all current-generation = consumer-grade routers. However, the operation can be constructed using log2(N) operations on = any modern CPU as a sequence of masks, shifts and adds. GCC has a = =E2=80=9Cbuiltin=E2=80=9D intrinsic function to use a popcnt instruction = where present, and this algorithm otherwise. Obviously this will only be of any use if the resulting hash is of good = quality. An obvious problem with popcnt is that inputs of 1, 2, 4, 8, = etc have the same popcnt (1), and it is trivial for an attacker to = exploit this property. - Jonathan Morton