From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eggs.gnu.org ([2001:4830:134:3::10]:48328) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ZKm7D-0005U5-JO for qemu-devel@nongnu.org; Thu, 30 Jul 2015 07:35:12 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1ZKm7A-0002Ei-7w for qemu-devel@nongnu.org; Thu, 30 Jul 2015 07:35:11 -0400 Received: from e19.ny.us.ibm.com ([129.33.205.209]:54809) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ZKm7A-0002EB-39 for qemu-devel@nongnu.org; Thu, 30 Jul 2015 07:35:08 -0400 Received: from /spool/local by e19.ny.us.ibm.com with IBM ESMTP SMTP Gateway: Authorized Use Only! Violators will be prosecuted for from ; Thu, 30 Jul 2015 07:35:07 -0400 From: Michael Roth Date: Thu, 30 Jul 2015 06:32:16 -0500 Message-Id: <1438255988-10418-2-git-send-email-mdroth@linux.vnet.ibm.com> In-Reply-To: <1438255988-10418-1-git-send-email-mdroth@linux.vnet.ibm.com> References: <1438255988-10418-1-git-send-email-mdroth@linux.vnet.ibm.com> Subject: [Qemu-devel] [PATCH 01/53] bt-sdp: fix broken uuids power-of-2 calculation List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: qemu-devel@nongnu.org Cc: Kevin Wolf , Andrzej Zaborowski , qemu-stable@nongnu.org, Stefan Hajnoczi From: Stefan Hajnoczi The binary search in sdp_uuid_match() only works when the number of elements to search is a power of two. lo = record->uuid; hi = record->uuids; while (hi >>= 1) if (lo[hi] <= val) lo += hi; return *lo == val; I noticed that the record->uuids calculation in sdp_service_record_build() was suspect: record->uuids = 1 << ffs(record->uuids - 1); Unlike most ffs(val) - 1 users, the expression is ffs(val - 1)! Actually ffs() is the wrong function to use for power-of-2. Use pow2ceil() to achieve the correct effect. Now the record->uuid[] array is sized correctly and the binary search in sdp_uuid_match() should work. I'm not sure how to run/test this code. Cc: Andrzej Zaborowski Cc: qemu-stable@nongnu.org Signed-off-by: Stefan Hajnoczi Message-id: 1427124571-28598-2-git-send-email-stefanha@redhat.com Signed-off-by: Kevin Wolf (cherry picked from commit 588ef9d411339012fc3c94bfad8911e9d0a517a2) Signed-off-by: Michael Roth --- hw/bt/sdp.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/hw/bt/sdp.c b/hw/bt/sdp.c index 218e075..c903747 100644 --- a/hw/bt/sdp.c +++ b/hw/bt/sdp.c @@ -707,7 +707,7 @@ static void sdp_service_record_build(struct sdp_service_record_s *record, len += sdp_attr_max_size(&def->attributes[record->attributes ++].data, &record->uuids); } - record->uuids = 1 << ffs(record->uuids - 1); + record->uuids = pow2ceil(record->uuids); record->attribute_list = g_malloc0(record->attributes * sizeof(*record->attribute_list)); record->uuid = -- 1.9.1