220 40371 article Path: news.gmane.org!.POSTED!not-for-mail From: Phil Miller Newsgroups: gmane.comp.lang.c++.isocpp.proposals Subject: =?UTF-8?B?UmU6IFtzdGQtcHJvcG9zYWxzXSBSZTogW1thc3NlcnQ6IGRpc2pvaW50KC4uLildXTogQw==?= =?UTF-8?B?b250cmFjdCBhc3NlcnRpb25zIGFzIGFuIGFsdGVybmF0ZSBzcGVsbGluZyBvZiDigJhyZXN0cmljdA==?= =?UTF-8?B?4oCZ?= Date: Mon, 8 Oct 2018 00:04:55 -0400 Lines: 296 Approved: news@gmane.org Message-ID: References: <48fe1f8b-c381-4c78-818b-2b606b0e89ad@isocpp.org> Reply-To: std-proposals@isocpp.org NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: multipart/alternative; boundary="0000000000001598610577afba23" X-Trace: blaine.gmane.org 1538971384 30216 195.159.176.226 (8 Oct 2018 04:03:04 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Mon, 8 Oct 2018 04:03:04 +0000 (UTC) Cc: "Szaday, Justin Josef" , David Hollman To: std-proposals@isocpp.org Original-X-From: std-proposals+bncBCSLDEHDREGRB5NO5POQKGQEFFNULXI@isocpp.org Mon Oct 08 06:02:59 2018 Return-path: Envelope-to: gclcip-std-proposals@m.gmane.org Original-Received: from mail-lj1-f200.google.com ([209.85.208.200]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1g9Ml1-0007lL-I4 for gclcip-std-proposals@m.gmane.org; Mon, 08 Oct 2018 06:02:59 +0200 Original-Received: by mail-lj1-f200.google.com with SMTP id t18-v6sf6422659ljc.23 for ; Sun, 07 Oct 2018 21:05:10 -0700 (PDT) ARC-Seal: i=2; a=rsa-sha256; t=1538971510; cv=pass; d=google.com; s=arc-20160816; b=Lz/XkiF7Jsuyb886e+wYjLL4/sR0XP2FBYGRCKb2QU79Ml5tlBGXlHZCLsi4Pgx9bC 7ChDPR2o2InUOXG6OmCGp6Fu3y/35AnFmfNNiSntXWyk4h+r7YMsi1RiX7HMUwtSPYfs PP4aDstTieVU/VtPjhpPUPeC2HeJ2/Y2W/xj5Bdt4EixwaILy44a9Hy+VAFGNNaLLmIa b8WvhkwpmWeTS7Dgmh++m+iobTymD86nhoUNDmRHts3WyR/UfpKqYHVTBs/tSghZm/qm 8SRhgotfzAg7DtWzTF99/JFpMLZkGysFvOMs3/LGMKNHmLkDmPcJiSe2Aqdyw2EWOXoF uSvQ== ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:reply-to:cc:to:subject:message-id :date:from:in-reply-to:references:mime-version:dkim-signature; bh=Irxz85A1JlvrX8Amkmeozp56NLFcOKTefjMKYP/g48o=; b=AIaFv3rL8DZWSBB98laP1EL8asrMQL1TtDKaiVbjtfqFdRe9Ou+6LmK0ZMwJBUJUSY GkKOV6n1yu7Ts/YcD11BvhkAREG1OYxTEFTmjTd12dNwCSO1ZlqntzWL8dKu30GW9rk1 9RtbbnGiS1iwXT4cAR4VnvXW2tOZxyDXIxNhQfWby4Vc+44CIg0TZKg3zepfcYgVS7ZL aLaQ3bFfj3xf1412768KlWcnNPWiURCp3uFgXRU1yLSPxIEE9qXZ8Ou8FtLWQbsFwfss AwHDBPFhl+610W4WcGHYLEAbJTQiByDnqrcHkV3n8RD47sua2gVZ32qkMu31usYYMNKI /eGg== ARC-Authentication-Results: i=2; mx.google.com; dkim=pass header.i=@gmail.com header.s=20161025 header.b=io2M7sk8; spf=pass (google.com: domain of unmobile@gmail.com designates 209.85.220.41 as permitted sender) smtp.mailfrom=unmobile@gmail.com; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=isocpp-org.20150623.gappssmtp.com; s=20150623; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc:x-original-sender:x-original-authentication-results:reply-to :precedence:mailing-list:list-id:list-post:list-help:list-archive :list-subscribe:list-unsubscribe; bh=Irxz85A1JlvrX8Amkmeozp56NLFcOKTefjMKYP/g48o=; b=G4rWHqDhFYut8wC1TdnxEVaNXbumyKlwlQb1KK2WUOxjf3NWaeTijLfOvU2hodLt+D hK5QoyjOp4vTH37nZUn22AWODu7FWXVnZV9Ew15ZIJ3QCNDSPmpsbWsK0DohU9J2D7sV 7EbfLCXueET4kwILDheKu71xbxNnzs4duMaqIENLYYaZYrPSw8NhsTw9GU6pfmpv5I4i 62vpLtFFC6I+YgzxtuvNT1IIWt70N3iU+ZsJj9DHrPI+dbqKtTQR8VyJYEG2DZukmu0f Nph0PH3frPAB8+YzbRdyJhFTNBEokgdKI0HOqffuMhN8NdaBxhm+5sdlsp1QGn/JEpJT Easw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc:x-original-sender :x-original-authentication-results:reply-to:precedence:mailing-list :list-id:x-spam-checked-in-group:list-post:list-help:list-archive :list-subscribe:list-unsubscribe; bh=Irxz85A1JlvrX8Amkmeozp56NLFcOKTefjMKYP/g48o=; b=fidzCUueSQGrcKsTNNoFMdm5l347wcWR55YZr9Eq6yugPDu1UsjDTx9IK4DnQ6E8Cs yLadHJzE8RJWJ5MUx9cElL6++A24Vbp5rnjAwvOujhBOTI4z5I/hLDgYNme1K3R0puve 9nLjmXBwFP3AHmecaKuTPwyVQk6y/9w+Np9cb4FO3H+ockWphFxo//PVOhVvQy21LHrL FWPeiHoNt6UVPHtpv/7KXIA1q3m/h8D26raZmEjqMc7GzrrTcD20BtS6yYcToCBOT2Lp OkChI/Stq5FccsBOCU/mSjzq0JvAhjG4N1cgNMZQ6PyLcRqS/g+zFIJO7s5brjrWUA/+ X04w== X-Gm-Message-State: ABuFfoh52y03X5FfqMD90bcsZslJL/DeInd9S8nEb33+EPuBrZ2Ynr1b uiRLEluKzvVh/+grScGcx5+nYA== X-Google-Smtp-Source: ACcGV62sqBqWJC3+IcE7IVqeHL739eWMpUSGfzXRZ4A8pGCYCH5EKkv2dI0Fm32/ygDFXP2VaNugwg== X-Received: by 2002:ac2:4259:: with SMTP id m25-v6mr535514lfl.38.1538971510311; Sun, 07 Oct 2018 21:05:10 -0700 (PDT) X-BeenThere: std-proposals@isocpp.org Original-Received: by 2002:a2e:6354:: with SMTP id x81-v6ls713274ljb.15.gmail; Sun, 07 Oct 2018 21:05:09 -0700 (PDT) X-Received: by 2002:a2e:2942:: with SMTP id u63-v6mr13372476lje.28.1538971509107; Sun, 07 Oct 2018 21:05:09 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1538971509; cv=none; d=google.com; s=arc-20160816; b=fklMvMEwQh9N6ALxDdQRcTLrI308/n1+QsxVSQyjj2tz1C1unqeDdky+yZ2zd5PZbM 1TRxdpDRfKNZqVPp0r1pOWRLxJ+6mHmy9b6jhBJEmVyys/3evfyviTFqaJpUlLJJt+Pq Y7p7Fg0LfkZLHzGy3flrP5R8jKa5JbFTzQZ4XVXmfDB2FWHvS5zOARUs52BNmvXK9n10 b9CtPIMGDYUmcvAaucBEYXxOI71nk6emh/w19DT8LKFloKu4tE/RhOTCKT5KkFRfyk6I o+kLr7i9mQKXSRzbaWH0Iq+6O7+ix2flWXDnGBwCdbh5Mf+mJVBtiQx6MNFroKb/0qgq En8Q== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:dkim-signature; bh=7lW7SSyWP0bv+iMsImqzDqUWSGYPdFIdMk9QHEcEWdw=; b=XsNp8S1B6xZye4vSy+ULnZUDMNWIjEn1fCLAl0LI0LqL1v8QJsi8IxAFm9TuhGMjw9 fpAYzMd/MHmhbHFWGzGSI2yu0kqmwPIAESqYW6T9dMzc91Ig5Q4uzWxwijAyC84Ewd/9 ka5wnay7UWb1ZAsjkDubPFMtsG0aegw5aZMOCsy3OTmoW1vRv5NyQ8ThNZ1rmk6aL0sM FgPuP2a0AXNnMTRCU2zXIrbKotXR+gqxPwG/BhNO1GaS2UW9AtT1IkN+41IfIaA8pcvH Pv7LLJ/RxXRfXJafUqQoFWJHpeeVdPX9QrchoPzyURQ5eO4S+m7CPXTjjE5ijf6YV7LO mqKg== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gmail.com header.s=20161025 header.b=io2M7sk8; spf=pass (google.com: domain of unmobile@gmail.com designates 209.85.220.41 as permitted sender) smtp.mailfrom=unmobile@gmail.com; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com Original-Received: from mail-sor-f41.google.com (mail-sor-f41.google.com. [209.85.220.41]) by mx.google.com with SMTPS id h22-v6sor7262537ljf.19.2018.10.07.21.05.09 for (Google Transport Security); Sun, 07 Oct 2018 21:05:09 -0700 (PDT) Received-SPF: pass (google.com: domain of unmobile@gmail.com designates 209.85.220.41 as permitted sender) client-ip=209.85.220.41; X-Received: by 2002:a2e:9bd0:: with SMTP id w16-v6mr13532831ljj.55.1538971508511; Sun, 07 Oct 2018 21:05:08 -0700 (PDT) In-Reply-To: <48fe1f8b-c381-4c78-818b-2b606b0e89ad@isocpp.org> X-Original-Sender: unmobile@gmail.com X-Original-Authentication-Results: mx.google.com; dkim=pass header.i=@gmail.com header.s=20161025 header.b=io2M7sk8; spf=pass (google.com: domain of unmobile@gmail.com designates 209.85.220.41 as permitted sender) smtp.mailfrom=unmobile@gmail.com; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com Precedence: list Mailing-list: list std-proposals@isocpp.org; contact std-proposals+owners@isocpp.org List-ID: X-Spam-Checked-In-Group: std-proposals@isocpp.org X-Google-Group-Id: 399137483710 List-Post: , List-Help: , List-Archive: List-Subscribe: , List-Unsubscribe: , Xref: news.gmane.org gmane.comp.lang.c++.isocpp.proposals:40371 Archived-At: --0000000000001598610577afba23 Content-Type: text/plain; charset="UTF-8" On Sun, Oct 7, 2018 at 11:35 PM Arthur O'Dwyer wrote: > On Saturday, October 6, 2018 at 9:55:04 AM UTC-7, Phil Miller wrote: >> >> Present Proposal >> >> Add a free function defined as follows to namespace std, in an >> appropriate header TBD: >> >> template >> >> bool disjoint(const T* pt, size_t nt, const U* pu, size_t nu) >> >> { >> >> intptr_t bt = pt, et = pt+nt; >> >> intptr_t bu = pu, eu = pu+nu; >> >> return (et <= bu) || (eu <= bt); >> >> } >> >> Requirements: >> >> - >> >> The pointers pt and pu are valid. >> - >> >> The expressions pt+nt and pu+nu are valid. (i.e. they point to >> elements within the same array as pt and pu, respectively, or to one past >> the end, including the case where pt is a pointer is to a non-array object >> and nt is 1 (or pu and nu, respectively)) >> >> > I don't know if this nit is really relevant to the rest of the proposal, > but that definition of `disjoint` has problems with boundary conditions, > e.g. if (et < bt) or (eu < bu). (I mean, if the addition bt+nt would have > overflowed.) It would be interesting and useful to come up with a > bulletproof definition of `disjoint` that actually worked in practice, just > to get the implementation out there in the wild, even if it never gets > standardized. > Hi Arthur, Thanks for the feedback. The latter requirement about the validity of expressions pt+nt was meant to cover the case noted, but I think it actually covers the overflow case you bring up as well. That overflow is UB, I believe, and is also very likely forming a pointer outside the bounds of the object pointed to by pt. So, I think the nit *is* relevant to the proposal, in that it's another case to note as forbidden by the requirement that the end-pointer expressions be valid. Does that seem right to you? At any rate, I've actually written roughly the necessary logic for the 'bullet-proof' version previously, in a different setting, so it's not too hard to reproduce an attempt at it here: template bool disjoint(const T* pt, size_t nt, const U* pu, size_t nu) { intptr_t bt = pt; intptr_t bu = pu; if (bt == bu) return false; if (bt < bu) { return (bu - bt) < (sizeof(T) * nt); } else { return (bt - bu) < (sizeof(U) * nu); } } The general idiom for avoiding the overflow in the addition is to compare the relevant distances instead. As formulated here, this of course still has potential overflows in the multiplication expressions. Then we get into the finicky business of rounding the difference up and dividing by sizeof(T), while making sure that the tested condition still means what we want it to. Phil -- You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group. To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org. To post to this group, send email to std-proposals@isocpp.org. To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/CAMDbWJFVVUxL%3D3XaDnJNqTvNK7Mc8PPAMusu9_JdcSvOc%2BXc%2BA%40mail.gmail.com. --0000000000001598610577afba23 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable


On Sun= , Oct 7, 2018 at 11:35 PM Arthur O'Dwyer <arthur.j.odwyer@gmail.com> wrote:
On Saturday, October 6, 2018 at 9= :55:04 AM UTC-7, Phil Miller wrote:
Present Proposal

Add a free function defined as follows to namespace= std, in an appropriate header TBD:


template <type= name T, typename U>

bool disjoint(const T* pt, size_t = nt, const U* pu, size_t nu)

{

=C2=A0in= tptr_t bt =3D pt, et =3D pt+nt;

=C2=A0intptr_t bu =3D pu= , eu =3D pu+nu;


=C2=A0return (et <=3D bu) || (eu = <=3D bt);

}


Requirements:

  • The pointers pt and pu are val= id.

  • The expressions pt+nt and pu+nu are valid. (i= ..e. they point to elements within the same array as pt and pu, respectively= , or to one past the end, including the case where pt is a pointer is to a = non-array object and nt is 1 (or pu and nu, respectively))

    • <= /ul>

I don't know if this nit is = really relevant to the rest of the proposal, but that definition of `disjoi= nt` has problems with boundary conditions, e.g. if (et < bt) or (eu <= bu). =C2=A0(I mean, if the addition bt+nt would have overflowed.) =C2=A0It= would be interesting and useful to come up with a bulletproof definition o= f `disjoint` that actually worked in practice, just to get the implementati= on out there in the wild, even if it never gets standardized.
=C2=A0
Hi Arthur,

Thanks= for the feedback. The latter requirement about the validity of expressions= pt+nt was meant to cover the case noted, but I think it actually covers th= e overflow case you bring up as well. That overflow is UB, I believe, and i= s also very likely forming a pointer outside the bounds of the object point= ed to by pt. So, I think the nit is relevant to the proposal, in tha= t it's another case to note as forbidden by the requirement that the en= d-pointer expressions be valid. Does that seem right to you?

=
At any rate, I've actually written roughly the necessary log= ic for the 'bullet-proof' version previously, in a different settin= g, so it's not too hard to reproduce an attempt at it here:
<= br>

template <typename T, typename U>

bool disjoint(const T* pt, size_t nt, const U* pu, size_t nu)

{

=C2=A0intptr_t bt =3D pt;


if (bt =3D=3D b= u)

return false;


if (bt < b= u) {

return (bu - bt) < (sizeof(T) * nt);

} else {=

<= span style=3D"font-size:11pt;font-family:"Courier New";color:rgb(= 0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-= variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre= -wrap"> return (bt - bu) < (sizeof(U) * nu);

}=

}


The general id= iom for avoiding the overflow in the addition is to compare the relevant di= stances instead. As formulated here, this of course still has potential ove= rflows in the multiplication expressions. Then we get into the finicky busi= ness of rounding the difference up and dividing by sizeof(T), while making = sure that the tested condition still means what we want it to.

Phil

--
You received this message because you are subscribed to the Google Groups &= quot;ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e= mail to std-proposa= ls+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/CAMDbWJFVVU= xL%3D3XaDnJNqTvNK7Mc8PPAMusu9_JdcSvOc%2BXc%2BA%40mail.gmail.com.
--0000000000001598610577afba23-- .