From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on inbox.vuxu.org X-Spam-Level: X-Spam-Status: No, score=-3.1 required=5.0 tests=DKIM_INVALID,DKIM_SIGNED, MAILING_LIST_MULTI,RCVD_IN_DNSWL_MED,RCVD_IN_MSPIKE_H3, RCVD_IN_MSPIKE_WL autolearn=ham autolearn_force=no version=3.4.4 Received: (qmail 4495 invoked from network); 1 Jul 2020 21:23:26 -0000 Received: from mother.openwall.net (195.42.179.200) by inbox.vuxu.org with ESMTPUTF8; 1 Jul 2020 21:23:26 -0000 Received: (qmail 7657 invoked by uid 550); 1 Jul 2020 21:23:22 -0000 Mailing-List: contact musl-help@lists.openwall.com; run by ezmlm Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: List-ID: Reply-To: musl@lists.openwall.com Received: (qmail 7639 invoked from network); 1 Jul 2020 21:23:21 -0000 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=0au.de; s=paul; h=In-Reply-To:Content-Type:MIME-Version:References:Message-ID:Subject :To:From:Date:Sender:Reply-To:Cc:Content-Transfer-Encoding:Content-ID: Content-Description:Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc :Resent-Message-ID:List-Id:List-Help:List-Unsubscribe:List-Subscribe: List-Post:List-Owner:List-Archive; bh=nRDwMRcnL6Bn6UgUyLCiCzHX7WV6ZpAuiQdOPO2MSc0=; b=ry2Gr409ymeOwDTIX82dzHrWTX e6giCZ/CL9/Dft88eMmjiIjsm+rSSxDIFUJpqFkFc/xst0tgt8jXiQTPxVUDPQDTK6BH1K0ELmtom +bxHx/dHwLK0F/EgiW5toG9+dX1LoAS2kUupu+byj8Go/8AoV57OWytaFrhT/rp0hhVPn/9qqAWvp 2tgwvUhL0zQzgtL93txPdwOMHjK2pcISCZzIZyqepD60tZVGq3JcRFxmGfyAZi0xk0Y+Oxi+YHcvg 49/wTMUb7gw5bnDmlQS6GUeaRCkf75mMWLmFrrj9ZPmN4zJere0fsk7+UXESG/xe9xtFw2DbMp3/J GsX3k6UHtcCAFpJQ/OVYoKhaDecQXq2p6EzzS/Bxec6GdiW32K9EEbCwLVergsA63QOE0zHrSf+y5 j76N9QnV2b0d0/60Ub8yCEa7G+HyQ2Y+Ps9dFkfcvvkNe2hecYskKE1qtnkvZ3FQdkBh4NwgqP+4c 9KgbbjJaQMBvnOrGHp/k/J8pbUW/YuZKvxvGhM3lXQXB0X/7kVgtKCl57BmPLarCW+K0jG0o7Tzbn sfold4FxtEIY757qiNSb3Q8ZyVcEIU4MlUGHrENYDtM7ulgZuBPdT37xQrs4uyBJbut6izQm8VH2m 8NqqiyYSabtrIA01KST3WOcy5xjLoBvZbqZQtSbiI=; Date: Wed, 1 Jul 2020 23:23:09 +0200 From: Valentin Ochs To: musl@lists.openwall.com Message-ID: <20200701212309.5ooyvfq47sh4llwi@mae> References: <20200701185026.GA6635@voyager> <20200701204456.GI6430@brightrain.aerifal.cx> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20200701204456.GI6430@brightrain.aerifal.cx> Subject: Re: [musl] Superfluous shift in qsort()? On Wed, Jul 01, 2020 at 04:44:56PM -0400, Rich Felker wrote: > On Wed, Jul 01, 2020 at 08:50:26PM +0200, Markus Wichmann wrote: > > Hi all, > > > > I noticed something while reading code today: Near the end of qsort(), > > we have this gem: > > > > shl(p, 2); > > pshift -= 2; > > p[0] ^= 7; > > shr(p, 1); > > > > Now, I don't know if I am missing something, but don't the shl and the > > shr partially cancel out? Isn't this the same as > > > > shl(p, 1); > > p[0] ^= 3; > > > > As it is, it isn't wrong, just weird. > > Assuming non-overflow, I think they're equivalent (also assuming you > keep the pshift-=2). Yes, it looks that way. I'm afraid I don't have any further insight - it's been quite a while since I thought about the qsort code, and I've not been doing much work on algorithms over the last couple of years. The only thing I can think of is that one could figure out which behaviour with regard to overflow in shl() should be the valid one. I suspect that replacing it would be valid and this is some transformation I did while implementing smoothsort without realizing that this can be simplified. Cheers, Valentin