[C++] new + negatieve size

[Verwijderd]

Ik vroeg mij af wat de c++ standaard zegt over de volgende code:

code:

int main() {
    int size=-1;
    try {
        int * data = new int[size];
        if (data==NULL)
            printf("Failed to allocate data: No exception\n");
        else
            printf("Allocated Data Succesfull\n");
        }
    catch(std::bad_alloc & e) {
        printf("Failed to allocate data: std::bad_alloc\n");
        }
    catch(...) {
        printf("Failed to allocate data: other exception\n");
        }
    return 0;
    }

Is een negatieve size zogezegd undefined behaviour, of zou dat een exception moeten throwen? Op een SGI Irix bijvoorbeeld, geeft ie geen exception en krijg ik een valid pointer terug.

[schoene]

new [] verwacht een std::size_t als parameter, en die is doorgaans (of altijd?) unsigned. Die -1 wordt dan gecast naar std::size_t en dat is volgens mij gelijk aan de max. waarde van std::size_t

[NMe]

Signed waarden hebben in het most significant bit een flag staan. Een signed char van is dus maar 7-bits, in plaats van 8-bits, omdat het achtste bitje gebruikt wordt voor het teken.

Bij negatieve getallen is dit teken 1, bij positieve 0. Verder werkt het tellen gewoon hetzelfde AFAIK, dus -1 zou dan bij een char deze waarde zijn: 10000001, wat unsigned weer overeen komt met 0x81 = 129.

Een goeie compiler zal er trouwens echter waarschijnlijk over beginnen te miepen.

[TheBlasphemer]

Volgens mij is size_t 32-bit op 32-bit systemen
-1 komt dus overeen met 0xFFFFFFFF (~4GB)
Theoretisch zou C++ hier mee om moeten gaan, maar in de praktijk kan dit natuurlijk niet, met 32-bit pointers kun je dit namelijk maximaal "aansturen", maar er moet ook ruimte overblijven voor de programmacode zelf in het geheugen

[schoene]

wordt de 2-complement methode niet gebruikt voor binaire representatie van negatieve waarden?
1) het positieve getal inverteren
2) 1 erbij optellen

dus: 1 heeft de binaire waarde 0000 0001

om -1 te hebben gebeurt het volgende:

inverteren: 1111 1110
1 optellen: 1111 1111

en unsigned is dat dus de max value

ben het niet zeker, want dat zit ver in het geheugen

edit: was dus reactie op NME

[ Voor 5% gewijzigd door schoene op 22-03-2006 16:58 ]

[Verwijderd]

Ik dacht dat de expressie 'new T()' altijd een object van het type T oplevert, en dus nooit 0 kan zijn. Mocht het object niet geconstrueerd kunnen worden, dan wordt std::bad_alloc gethrowd, om zodoende de lokale scope te verlaten waardoor het 'mislukte' object vernietigd wordt. Dit omdat je anders een pointer naar een ongeldig object hebt en deze per ongeluk zou kunnen gebruiken.

[NMe]

Hmm, nou je het zegt, dat zou eigenlijk best kunnen.

Ik vermijd situaties waarin ik signed en unsigned moet combineren altijd, dus ik kom het niet vaak tegen. De laatste keer dat ik er wat over zag was in de eerste klas van mijn HBO-opleiding.

[.oisyn]

NMe heeft het idd bij het verkeerde eind, het 2 complement systeem wordt gewoon gebruikt. Dit is handig omdat berekeningen dan niet anders zijn voor signed dan voor unsigned getallen: (signed char)0 - (signed char)1 geeft natuurlijk -1, maar dat is gelijk aan 0xff, waardoor het voor unsigned chars dus hetzelfde resultaat oplevert. Dit geldt ook voor vermenigvuldigingen (3 * 0xff = 0xfd = 3 * -1 = -3).

schoene heeft idd gelijk dat size_t een unsigned waarde is en dat je dus eigenlijk std::numeric_limits<size_t>::max() als het aantal elementen in de array gebruikt. En dit geeft vrijwel altijd een exception

[ Voor 21% gewijzigd door .oisyn op 22-03-2006 17:06 ]

[.oisyn]

TheBlasphemer schreef op woensdag 22 maart 2006 @ 16:55:
Volgens mij is size_t 32-bit op 32-bit systemen
-1 komt dus overeen met 0xFFFFFFFF (~4GB)
Theoretisch zou C++ hier mee om moeten gaan, maar in de praktijk kan dit natuurlijk niet, met 32-bit pointers kun je dit namelijk maximaal "aansturen", maar er moet ook ruimte overblijven voor de programmacode zelf in het geheugen

Let wel, een array van 0xffffffff ints, de totale grootte van de array is dus sizeof(int) * 0xffffffff = 0xfffffffc

[Verwijderd]

De meeste compilers die ik getest heb throwen trouwens een bad_alloc met -1. Behalve VC6 (die zoiezo niks throwt) en SGI. Als je de -1 vervangt door -100 dan throwt de SGI compiler trouwens wel.

[.oisyn]

Overigens wordt je new handler ook eerst aangeroepen als je die hebt ingesteld met set_new_handler, dus een throw hoeft sowieso niet per se.

[MSalters]

.oisyn schreef op woensdag 22 maart 2006 @ 17:04:
NMe heeft het idd bij het verkeerde eind, het 2 complement systeem wordt gewoon gebruikt.

Hoeft niet. 1 complement mag bijvoorbeeld ook.

[.oisyn]

I stand corrected.

[Daos]

offtopic:
Bij 1's complement neem je gewoon de inverse van een getal om het negatief te krijgen.
NME heeft het over "signed magnitude". Dit systeem zie je tegenwoordig niet zo veel meer. Vermenigvuldigen gaat in hardware iets makkelijker dan bij 2's complement.

[.oisyn]

Hoezo iets makkelijker, bij vermenigvuldigen in 2's complement hoef je anders geen rekening te houden met het teken, zoals ik in mijn vorige post gedemonstreerd heb:
0xF2 * 0xF8 mod 256 = 0xEA70 mod 256 = 0x70
-14 * -8 mod 256 = 112 = 0x70

[Daos]

.oisyn schreef op donderdag 23 maart 2006 @ 10:27:
Hoezo iets makkelijker, bij vermenigvuldigen in 2's complement hoef je anders geen rekening te houden met het teken, zoals ik in mijn vorige post gedemonstreerd heb:
0xF2 * 0xF8 mod 256 = 0xEA70 mod 256 = 0x70
-14 * -8 mod 256 = 112 = 0x70

Dat komt omdat je de hoge bits weggooit (zoals ook meestal gebeurt bij een hoge taal zoals C, Java). Een processor doet dit niet en geeft bv 64 bits (EDX:EAX) terug als je 2 32 bits getallen met elkaar vermenigvuldigt. Bij veel processors zijn er aparte instructies voor signed en unsigned vermenigvuldiging (mul en imul).

Goed vermenigvuldigen met 2's complement kan wel (bv modified Baugh Wooley), maar dit is iets moeilijker dan een unsigned vermenigvuldiging.

[.oisyn]

Daos schreef op donderdag 23 maart 2006 @ 21:42:
Een processor doet dit niet en geeft bv 64 bits (EDX:EAX) terug als je 2 32 bits getallen met elkaar vermenigvuldigt.

Beetje raar als je het over "een processor" hebt terwijl je eigenlijk specifiek op de x86 ingaat, maar goed.

Jij hebt het hier over de mul of imul instructie met 1 operand, die eax met die operand vermenigvuldigt en het antwoord en edx:eax zet. Als je ze echter met 2 operanden gebruikt vermenigvuldig je de ene met de ander en komt het resultaat ook gewoon in een van die twee. Geen antwoord in edx:eax dus, maar gewoon een normaal 32 bits antwoord in een enkel register naar keuze. De reden voor het verschil tussen een mul en imul instructie zit 'm in de flags die ze zetten afhankelijk van het antwoord, en natuurlijk de sign extension voor het 64 bits antwoord bij de imul. Dat wil niet zeggen dat de schakelingen die voor de vermenigvuldigingen zorgen anders zijn voor de twee instructies, en dat bedoelen we neem ik aan met de daadwerkelijke hardware implementatie voor de vermenigvuldiging.

Dus als je niet geïnteresseerd bent in flags en je wilt gewoon een antwoord met hetzelfde aantal bits als de invoer dan zijn de vermenigvuldigingen voor signed en unsigned getallen in het 2's complement systeem niet verschillend. Daarom heeft de ARM van de gameboy die ik toevallig ken ook maar 1 soort mul instructie, als ik me het goed herinner. En of je 'm nou voor signed of unsigned getallen gebruikt, dat maakt niet uit.

[ Voor 22% gewijzigd door .oisyn op 24-03-2006 00:29 ]

[Daos]

De hoogste bitjes zijn meer dan alleen sign extension. Als je twee 32 bits getallen vermenigvuldigt, dan past het resultaat altijd in 64 bits.

Voorbeeldje met 3 bits vermenigvuldiging:
unsigned: 3 * 5 decimaal = 011 x 101 binair

   011
   101
   --- *
   011
  000
 011
------ +
001111

001111 binair = 15 decimaal

2's complement: 3 * -3 decimaal = 011 x 101 binair (= zelfde als hierboven)
(gebruik modified Baugh Wooley van mijn vorige post)

   011
   101
   --- *
  1111
  100
1000
------ +
110111

110111 binair = -9 decimaal

Uit de unsigned vermenigvuldiging komt 001111 en uit de 2's complement vermenigvuldiging komt 110111 (iets anders dus).

[.oisyn]

Ok, als je antwoord een hogere resolutie heeft dan je input kan het niet zomaar, maar hoe is dat dan makkelijker met een sign/magnitude implementatie? Want dat was de hele strekking van je originele post. Ook daar zul je nog wat handelingen moeten doen om het goed te laten werken:

(unsigned)5 * 3 = 0b101 * 0b011 = 0b001111 = (unsigned) 15
(signed)-1 * 3 = 0b101 * 0b011 = 0b100011 = (signed) -3

Ook niet hetzelfde.

[Daos]

.oisyn schreef op vrijdag 24 maart 2006 @ 12:07:
Ok, als je antwoord een hogere resolutie heeft dan je input kan het niet zomaar, maar hoe is dat dan makkelijker met een sign/magnitude implementatie? Want dat was de hele strekking van je originele post. Ook daar zul je nog wat handelingen moeten doen om het goed te laten werken:

(unsigned)5 * 3 = 0b101 * 0b011 = 0b001111 = (unsigned) 15
(signed)-1 * 3 = 0b101 * 0b011 = 0b100011 = (signed) -3

Ook niet hetzelfde.

Bij sign/magnitude kan je gewoon de magnitudes met een unsigned multiplier vermenigvuldigen het resultaat hiervan is de magnitude van je antwoord. De sign van het antwoord bereken je parallel door de signs van de inputs in een xor te stoppen.
101 x 011 => sign = 1 xor 0 = 1, magnitude =

  01
  11
  -- *
  01
 01
---- +
0011

antwoord = 100011

Dit is simpeler omdat er een unsigned multiplier gebruikt wordt. Een unsigned multiplier is simpeler dan de 2's complement multiplier
Je moet inderdaad nog iets doen als je zowel sign/magnitude als unsigned wil gebruiken, maar dat is niet zoveel werk:

                    |/      |/ 32 bits         |  unsigned/ not(sm)
                   /|      /|                  |
                    |       |                  |
  /--------------------+----+                  |
  |  bit 31         |  |    |                  |
  |                 |  |    |                  |
  | /----------+----+  |    |                  |
  | |  bit 31  |    |/ |    |/ 31 bits         |
  | |          |   /|  |   /|                  |
  | |          |    |  |    |                  |
  | |          |    |  |    |                  |
  | |          | /-------+---------------------+
  | |          | |  |  | |  |                  |
  | |         [and] | [and] |                  |
  | |           |   |   |   |                  |
  | |           \---+   \---+                  |
  | |               |/      |/ 32 bits         |
  | |              /|      /|                  |
  | |               |       |                  |
  | |              \|/     \|/                 |
  | |             ------------                 |
  | |             |  32 bits |                 |
 [xor]            | unsigned |                 |
   |              |multiplier|                 |
   |              ------------                 |
   |                   |/ 64 bits              |
   |                  /|                       |
   |        bit 63     |                       |
   |  /----------------+                       |
   |  |                |/ 63 bits              |
  0| 1|               /|                       |
--------               |                       |
\ Mux  /---------------------------------------+
 ------                |
    |        bit 63    |
    \------------------+
                       |/ 64 bits
                      /|
                       |
                      \|/

[ Voor 46% gewijzigd door Daos op 24-03-2006 13:49 . Reden: "plaatje" ]

[.oisyn]

Wat nog altijd meer moeite is dan een generieke 2's complement multiplier die net zoveel bits teruggeeft als dat je erin stopt

[Olaf van der Spek]

.oisyn schreef op woensdag 22 maart 2006 @ 17:08:
Let wel, een array van 0xffffffff ints, de totale grootte van de array is dus sizeof(int) * 0xffffffff = 0xfffffffc

Volgens mij ben je een f vergeten.
Of neem je aan dat het een 32 bits systeem is.

[Soultaker]

In de standaard vind ik de volgende informatie:
• een throwing allocator moet std::bad_alloc throwen;
• een non-throwing allocator moet null returnen.
Een non-null pointer zou dus altijd op een geslaagde allocatie moeten duiden en dan moet de pointer dus ook naar een blok geheugen van de juiste grootte moeten wijzen. De vraag is dus hoe groot het blok is dat precies gealloceerd wordt; ik kan me voorstellen dat de compiler in het belang van de performance niet controleert of bij het vermenigvuldigen van size met sizeof(int) overflow plaatsvindt.

Wat is het resultaat van sizeof(int[size]) op het platform dat een non-null pointer retourneert?

[.oisyn]

OlafvdSpek schreef op zaterdag 25 maart 2006 @ 13:08:
[...]

Volgens mij ben je een f vergeten.
Of neem je aan dat het een 32 bits systeem is.

Als ik dat niet aannam was -1 ook niet gelijk aan 0xffffffff geweest