From patchwork Tue Apr 25 16:47:50 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Nathan Sidwell X-Patchwork-Id: 754928 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 3wC8KJ0KN2z9s5L for ; Wed, 26 Apr 2017 02:48:03 +1000 (AEST) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="UG0fKEWN"; dkim-atps=neutral DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:to :from:subject:message-id:date:mime-version:content-type; q=dns; s=default; b=kF8HGs/niWTAba+WRn+JVWZJDc8MlvlA4TaBEbgmFuu3VKE6XL Xhj1ZoEX7WwvoPlaYdfzUQUuWQrEs/dCV1QKeXCGuRw1RwWLdd/wFUD0LyVH38SE hE2+xJCrZUjNA0dYe5lVRD4bA2RPM4qo1EZcii3R6fQ3ijIQ43ZZaBLMI= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:to :from:subject:message-id:date:mime-version:content-type; s= default; bh=w9unObD+gPwjftPr7bJc36LQVXE=; b=UG0fKEWNxWCMno34RRpH TbHbaTf+Y1CVN5R4Q243H4mXynkIpH4tSsSlMST5KuaYgVkxaExAlRqcfcOFO2Nd LE0xH+K87uvo47f/HQ2s7Yk52SIE6LwBVRntcdiIg1eZrmsHgtt3TCv754sHoEiT bOOvpD9GJzvT2jyFr8v29Rw= Received: (qmail 8884 invoked by alias); 25 Apr 2017 16:47:53 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 8874 invoked by uid 89); 25 Apr 2017 16:47:52 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-10.6 required=5.0 tests=BAYES_00, FREEMAIL_FROM, GIT_PATCH_2, GIT_PATCH_3, KAM_ASCII_DIVIDERS, RCVD_IN_DNSWL_NONE, RCVD_IN_SORBS_SPAM, SPF_PASS autolearn=ham version=3.3.2 spammy=feedbacks, 5s, worker, feed X-HELO: mail-yw0-f181.google.com Received: from mail-yw0-f181.google.com (HELO mail-yw0-f181.google.com) (209.85.161.181) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Tue, 25 Apr 2017 16:47:51 +0000 Received: by mail-yw0-f181.google.com with SMTP id 203so95758589ywe.0 for ; Tue, 25 Apr 2017 09:47:53 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:sender:to:from:subject:message-id:date :user-agent:mime-version:content-language; bh=KyAI7n2qjos0RbdXMUxpPrywFbBlhUKVeRFeIkAL0ug=; b=kbsjyQ2M/44vb3AExD+dqeK13p9RvvrlO9HAdmltyn3SUGXNfXNnH4xUVDbfECFP26 ktUafhaBtgEU8pHD0xcZnynvZw8Lz3rUUB5zxktCu8ESiDwgI5l648BLxHyuB24LLEl1 M05He3gFvMaf+2OiPLFjIdxpLXJ9padlu2+qNYeCmfgAaXMPNb5YRDk6RF7DYqAMUvQC MBgNsXRpq+pyfVUH0iPeRd8K4zfdbg8VCQJoD3CHf242QVIUtMgmwdfPX+C8vddN9tU+ BXfjzr53RCphN1A+hND6pDXBgcYKWXaVCrezmfqtkOsBHClwflbN0R6GCEefyJkDuU28 To1w== X-Gm-Message-State: AN3rC/4Q1zxHS12WVkfqLGwbBHbwKyOKaHBwccSfayXZtWgnLBUfRmV4 ow/6zE+7o/O+Mw== X-Received: by 10.13.201.193 with SMTP id l184mr4657900ywd.73.1493138872042; Tue, 25 Apr 2017 09:47:52 -0700 (PDT) Received: from ?IPv6:2620:10d:c0a3:20fb:f6d0:5ac5:64cd:f102? ([2620:10d:c091:200::2:8903]) by smtp.googlemail.com with ESMTPSA id v3sm8802690ywi.79.2017.04.25.09.47.51 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Tue, 25 Apr 2017 09:47:51 -0700 (PDT) To: GCC Patches From: Nathan Sidwell Subject: [PATCH] Do CRC 4 bits at a time Message-ID: <78941ada-34a7-432f-f991-a0002a615797@acm.org> Date: Tue, 25 Apr 2017 12:47:50 -0400 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.0 MIME-Version: 1.0 Hi, our current CRC routine processes 1 bit at a time, and permits arbitrary numbers of bits from 1 to 32. However we only ever feed it multiples of 8 bits to process. So part of this patch changes the interface to use a crc32_unsigned_n worker function, which crcs a N-byte integer. The other change is to do 4 bits at a time. This is possible because the feedback syndrome is '0x04c11db7', which has the top 5 bits clear. But 5's an awkward number to work with, so just go with nibble at a time. bootstrapped on x86_64-linux, ok for trunk? nathan 2017-04-25 Nathan Sidwell * tree.h (crc32_unsigned_n): Declare. (crc32_unsigned, crc32_unsigned): Make inline. * tree.c (crc32_unsigned_bits): Replace with ... (crc32_unsigned_n): ... this. (crc32_unsigned, crc32_byte): Remove. (crc32_string): Remove unnecessary braces. Index: tree.c =================================================================== --- tree.c (revision 247207) +++ tree.c (working copy) @@ -9611,38 +9611,34 @@ dump_tree_statistics (void) #define FILE_FUNCTION_FORMAT "_GLOBAL__%s_%s" -/* Generate a crc32 of a byte. */ +/* Generate a crc32 of the low BYTES bytes of VALUE. */ -static unsigned -crc32_unsigned_bits (unsigned chksum, unsigned value, unsigned bits) +unsigned +crc32_unsigned_n (unsigned chksum, unsigned value, unsigned bytes) { - unsigned ix; - - for (ix = bits; ix--; value <<= 1) + /* This relies on the raw feedback's top 4 bits being zero. */ +#define FEEDBACK(X) ((X) * 0x04c11db7) +#define SYNDROME(X) (FEEDBACK ((X) & 1) ^ FEEDBACK ((X) & 2) \ + ^ FEEDBACK ((X) & 4) ^ FEEDBACK ((X) & 8)) + static const unsigned syndromes[16] = { - unsigned feedback; - - feedback = (value ^ chksum) & 0x80000000 ? 0x04c11db7 : 0; - chksum <<= 1; - chksum ^= feedback; - } - return chksum; -} - -/* Generate a crc32 of a 32-bit unsigned. */ + SYNDROME(0x0), SYNDROME(0x1), SYNDROME(0x2), SYNDROME(0x3), + SYNDROME(0x4), SYNDROME(0x5), SYNDROME(0x6), SYNDROME(0x7), + SYNDROME(0x8), SYNDROME(0x9), SYNDROME(0xa), SYNDROME(0xb), + SYNDROME(0xc), SYNDROME(0xd), SYNDROME(0xe), SYNDROME(0xf), + }; +#undef FEEDBACK +#undef SYNDROME -unsigned -crc32_unsigned (unsigned chksum, unsigned value) -{ - return crc32_unsigned_bits (chksum, value, 32); -} + value <<= (32 - bytes * 8); + for (unsigned ix = bytes * 2; ix--; value <<= 4) + { + unsigned feedback = syndromes[((value ^ chksum) >> 28) & 0xf]; -/* Generate a crc32 of a byte. */ + chksum = (chksum << 4) ^ feedback; + } -unsigned -crc32_byte (unsigned chksum, char byte) -{ - return crc32_unsigned_bits (chksum, (unsigned) byte << 24, 8); + return chksum; } /* Generate a crc32 of a string. */ @@ -9651,9 +9647,7 @@ unsigned crc32_string (unsigned chksum, const char *string) { do - { - chksum = crc32_byte (chksum, *string); - } + chksum = crc32_byte (chksum, *string); while (*string++); return chksum; } Index: tree.h =================================================================== --- tree.h (revision 247207) +++ tree.h (working copy) @@ -4688,9 +4688,18 @@ inlined_function_outer_scope_p (const_tr function_args_iter_next (&(ITER))) /* In tree.c */ +extern unsigned crc32_unsigned_n (unsigned, unsigned, unsigned); extern unsigned crc32_string (unsigned, const char *); -extern unsigned crc32_byte (unsigned, char); -extern unsigned crc32_unsigned (unsigned, unsigned); +static inline unsigned +crc32_unsigned (unsigned chksum, unsigned value) +{ + return crc32_unsigned_n (chksum, value, 4); +} +static inline unsigned +crc32_byte (unsigned chksum, char byte) +{ + return crc32_unsigned_n (chksum, byte, 1); +} extern void clean_symbol_name (char *); extern tree get_file_function_name (const char *); extern tree get_callee_fndecl (const_tree);