From patchwork Fri Mar 22 12:46:03 2013 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peter Lieven X-Patchwork-Id: 230005 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from lists.gnu.org (lists.gnu.org [208.118.235.17]) (using TLSv1 with cipher AES256-SHA (256/256 bits)) (Client did not present a certificate) by ozlabs.org (Postfix) with ESMTPS id 6E1782C00D0 for ; Sat, 23 Mar 2013 00:07:17 +1100 (EST) Received: from localhost ([::1]:50062 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1UJ1gh-00071e-8l for incoming@patchwork.ozlabs.org; Fri, 22 Mar 2013 09:07:15 -0400 Received: from eggs.gnu.org ([208.118.235.92]:40430) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1UJ1gB-0006sQ-Hr for qemu-devel@nongnu.org; Fri, 22 Mar 2013 09:06:50 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1UJ1g7-0004Ou-Jd for qemu-devel@nongnu.org; Fri, 22 Mar 2013 09:06:43 -0400 Received: from [2a02:248:0:30:223:aeff:fefe:7f1c] (port=45976 helo=dns.kamp-intra.net) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1UJ1N4-0005ZQ-9D for qemu-devel@nongnu.org; Fri, 22 Mar 2013 08:46:58 -0400 Received: from lieven-pc.kamp-intra.net (lieven-pc.kamp-intra.net [172.21.12.60]) by dns.kamp-intra.net (Postfix) with ESMTP id AF3A6206AC; Fri, 22 Mar 2013 13:46:57 +0100 (CET) Received: by lieven-pc.kamp-intra.net (Postfix, from userid 1000) id F19D362F00; Fri, 22 Mar 2013 13:46:57 +0100 (CET) From: Peter Lieven To: qemu-devel@nongnu.org Date: Fri, 22 Mar 2013 13:46:03 +0100 Message-Id: <1363956370-23681-3-git-send-email-pl@kamp.de> X-Mailer: git-send-email 1.7.9.5 In-Reply-To: <1363956370-23681-1-git-send-email-pl@kamp.de> References: <1363956370-23681-1-git-send-email-pl@kamp.de> X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6.x X-Received-From: 2a02:248:0:30:223:aeff:fefe:7f1c Cc: quintela@redhat.com, Stefan Hajnoczi , Peter Lieven , Orit Wasserman , Paolo Bonzini Subject: [Qemu-devel] [PATCHv4 2/9] cutils: add a function to find non-zero content in a buffer X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org Sender: qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org this adds buffer_find_nonzero_offset() which is a SSE2/Altivec optimized function that searches for non-zero content in a buffer. due to the optimizations used in the function there are restrictions on buffer address and search length. the function can_use_buffer_find_nonzero_content() can be used to check if the function can be used safely. Signed-off-by: Peter Lieven Reviewed-by: Eric Blake --- include/qemu-common.h | 13 +++++++++++++ util/cutils.c | 45 +++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 58 insertions(+) diff --git a/include/qemu-common.h b/include/qemu-common.h index e76ade3..078e535 100644 --- a/include/qemu-common.h +++ b/include/qemu-common.h @@ -472,4 +472,17 @@ void hexdump(const char *buf, FILE *fp, const char *prefix, size_t size); #define ALL_EQ(v1, v2) ((v1) == (v2)) #endif +#define BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR 8 +static inline bool +can_use_buffer_find_nonzero_offset(const void *buf, size_t len) +{ + if (len % (BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR + * sizeof(VECTYPE)) == 0 + && ((uintptr_t) buf) % sizeof(VECTYPE) == 0) { + return true; + } + return false; +} +size_t buffer_find_nonzero_offset(const void *buf, size_t len); + #endif diff --git a/util/cutils.c b/util/cutils.c index 1439da4..41c627e 100644 --- a/util/cutils.c +++ b/util/cutils.c @@ -143,6 +143,51 @@ int qemu_fdatasync(int fd) } /* + * Searches for an area with non-zero content in a buffer + * + * Attention! The len must be a multiple of + * BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR * sizeof(VECTYPE) + * and addr must be a multiple of sizeof(VECTYPE) due to + * restriction of optimizations in this function. + * + * can_use_buffer_find_nonzero_offset() can be used to check + * these requirements. + * + * The return value is the offset of the non-zero area rounded + * down to BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR * sizeof(VECTYPE). + * If the buffer is all zero the return value is equal to len. + */ + +size_t buffer_find_nonzero_offset(const void *buf, size_t len) +{ + VECTYPE *p = (VECTYPE *)buf; + VECTYPE zero = ZERO_SPLAT; + size_t i; + + assert(len % (BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR + * sizeof(VECTYPE)) == 0); + assert(((uintptr_t) buf) % sizeof(VECTYPE) == 0); + + if (*((const long *) buf)) { + return 0; + } + + for (i = 0; i < len / sizeof(VECTYPE); + i += BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR) { + VECTYPE tmp0 = p[i + 0] | p[i + 1]; + VECTYPE tmp1 = p[i + 2] | p[i + 3]; + VECTYPE tmp2 = p[i + 4] | p[i + 5]; + VECTYPE tmp3 = p[i + 6] | p[i + 7]; + VECTYPE tmp01 = tmp0 | tmp1; + VECTYPE tmp23 = tmp2 | tmp3; + if (!ALL_EQ(tmp01 | tmp23, zero)) { + break; + } + } + return i * sizeof(VECTYPE); +} + +/* * Checks if a buffer is all zeroes * * Attention! The len must be a multiple of 4 * sizeof(long) due to