Bit in Pointer speichern

RHBaum

IMHO sind Pointer auf
Linux/Windows, 32/64 bit, gerade. Stimmt das immer (und warum)?

definitiv nicht.
Es gibt zwar meist ein 4 byte alignment, das verhindert aber nicht ungerade Pointer.
Einfaches beispiel zum nachvollziehen:
const char testchar[] = "Test";

void * p1 = &testchar[0]; p1 wird wohl nicht nur gradzahlig sein
void * p2 = &testchar[1]; Preisfrage: ist p2 auch gradzahlig ???

Ergo: so richtig sicher kannst du Dir nie sein, ob ein ungerader pointer nur durch manipulation zustande kam oder ob er wirklich auf das zeigt auf was er wirklich zeigen soll.

Ganz lustig wird dann sicher, wenn man den speicher ned selber allokiert, sondern allokatoren ans werk laesst. Wer garantiert, das die auch alignment verwenden ? (hoechstwahrscheinlich werden sie es, aber 100% garantiert isses sicher ned)

Ciao ...

geom

Jockelx schrieb:

Nicht, das ich das Vorgehen verteidigen will, aber gemeint war wohl eher sowas:

Wegen dem Alignment zeigt ein Pointer auf was gerades.
Zeigt er auf etwas ungerades, dann kann man daraus schliessen, dass da ein Bit per Hand gesetzt wurde.

So hab ich das verstanden. Also machbar aber schwachsinn.

Ja, so ist das gemeint. Die Frage war, ob das sicher ist, was bei Geradzahligkeit
gegeben sein sollte. Schwachsinn, warum?

hustbaer

Wirklich saubere Lösung gibts da eigentlich nur eine: statt eines Pointers nen Index in ein Array verwenden. Dann kann man selbst kontrollieren wie gross der Index maximal werden kann, und alle unbenutzten Bits für etwas anderes verwenden.

(Muss natürlich nicht ein Index in ein flaches Array sein, gibt ja noch Maps und B-Bäume und was nicht noch alles)

Alles andere ist ein mehr oder weniger schlimmer Hack.

p.S.: wenn der Typ auf den so ein Zeiger zeigt halbwegs gross ist, dann hat man sehr gute Chancen dass alignof(T) grösser 1 ist, und eine Zweierpotenz (also gerade). Wenn man dann nirgends pfuscht, heisst das auch, dass alle Zeiger die auf so einen Typ zeigen einen geraden Wert haben.

Ich würde es allerdings nicht machen wollen. Der Trick ist alt und wurde oft eingesetzt, und viele sind damit früher oder später auf die Schnauze gefallen. Wäre mir einfach zu riskant.

RHBaum

Schwachsinn, warum?

- gefaehrlich
- sehr ungewoehnlich, selbst wenns funktioniert. Damit überraschender / unüblicher Code -> schwer wartbar.

und für was ?
Auf welchen System hat man so speichernot ? wenn ich mir anschaue was allein durchs Alignment verschenkt werden kann, dann waeren 8 statt 4 byte pro Pointer nur ein relativ geringes Übel

Dann waer vielleicht ne Option, nen 16bit compiler rauszukramen und das prog als "small" zu compilieren, dann haben pointer nur 2 byte verbrauch. Nachteil, man müsste extra ne 16bit runtime für starten Oder den rechner mit dieser speichernot ned eh nur im realmode unter Dos/irgendwa anderes mit 16bit laufen lassen Ne GUI bei dem speichermangel ist doch eh nen no go

Ciao ...

Jockelx

RHBaum schrieb:

void * p1 = &testchar[0]; p1 wird wohl nicht nur gradzahlig sein
void * p2 = &testchar[1]; Preisfrage: ist p2 auch gradzahlig ???

Hat mit der Frage nichts zu tun.

geom schrieb:

Schwachsinn, warum?

Wurde doch schon beantwortet. Oder nochmal gefragt:
Warum hast du unter Linux und Windows zu wenig Speicherplatz, um auf sowas zurückgreifen zu müssen?

geom

(Erstmal sorry, den Originalpost habe ich als Unregistrierter gemacht. Hatte
die Userdaten nicht gleich bei der Hand..)

Es handelt sich um eine Datenstruktur, die aus kleinen Objekten, die Pointer
enthalten, gebildet wird. Für diese Objekte wird ein Zustand benötigt. Da
nahezu der ganze Speicherbedarf sich auf diese kleinen Objekte bezieht - je
nach Datensatz können das mehrere GB sein - wäre ein Overhead dort gleich
dem Overhead des gesamten Speicherbedarfs.

Lösung 1: Verwende ein Set. Das kostet Zeit.
Lösung 2: Verwende einen bool im Objekt. Das kostet durch das Alignment
mehrere Bytes statt einem einzigen Bit.
Lösung 3: Mache einen der Pointer ungerade, um den Zustand als gesetzt zu
markieren. Häßlich.

Jede Lösung weist Nachteile auf. Da nur ein kurzer Abschnitt des Algorithmus
betroffen ist, scheint mir die Häßlichkeit von Lösung drei akzeptabel, sofern
die Möglichkeit, das _sicher_ zu machen, gegeben ist.

lg

geom schrieb:

Lösung 1: Verwende ein Set. Das kostet Zeit.

Und das umbiegen und rumcasten von Zeigern kostet keine Zeit?

rean

Falls deine Objekte z.B. in einem Array liegen und sich deren Indizes nicht oder nachvollziehbar ändern könntest du parallel dazu eine bitlist mit deinen Zuständen anlegen.

Caligulaminus

Etwa so?

template <typename T>
class hellPtr
{
	T* ptr_;
public:
	hellPtr():ptr_(0){};
	hellPtr(T* ptr):ptr_(ptr){};
	T* operator ->(){return (T*)((unsigned int)ptr_ & 0xFFFFFFFE);};
	T& operator *(){return *((T*)((unsigned int)ptr_ & 0xFFFFFFFE));};
	void operator=(T* ptr){ptr_=ptr;};
	operator T*(){return (T*)((unsigned int)ptr_ & 0xFFFFFFFE);};
	bool getflag(){return (bool)((unsigned int)ptr_ & 1L);};
	void setflag(bool b){if(b) ptr_=(T*)((unsigned int)ptr_ | 1L); else ptr_=(T*)((unsigned int)ptr_ & 0xFFFFFFFE);};
};

Ist jetzt hart für 32 Bit, funktioniert aber (soweit meine Tests gingen).

Ich würde aber auch eher abraten...

~Lecker! - Braten ~

geom

Caligulaminus schrieb:

Etwa so?

template <typename T>
class hellPtr
{
	T* ptr_;
public:
	hellPtr():ptr_(0){};
	hellPtr(T* ptr):ptr_(ptr){};
	T* operator ->(){return (T*)((unsigned int)ptr_ & 0xFFFFFFFE);};
	T& operator *(){return *((T*)((unsigned int)ptr_ & 0xFFFFFFFE));};
	void operator=(T* ptr){ptr_=ptr;};
	operator T*(){return (T*)((unsigned int)ptr_ & 0xFFFFFFFE);};
	bool getflag(){return (bool)((unsigned int)ptr_ & 1L);};
	void setflag(bool b){if(b) ptr_=(T*)((unsigned int)ptr_ | 1L); else ptr_=(T*)((unsigned int)ptr_ & 0xFFFFFFFE);};
};

Ist jetzt hart für 32 Bit, funktioniert aber (soweit meine Tests gingen).

Ich würde aber auch eher abraten...

~Lecker! - Braten ~

Oh, ein Smart-Pointer aus der Hölle Gute Idee.

Ich habe gerade die Alternativen getestet: Die Lösung mit dem bool, der
Speicher kostet, braucht 5.1s. Eine Lösung mit einem STL set braucht 70s,
und ein unordered_set etwa gleich lange. Indexlösungen schätze ich wegen
der indirekten Adressierung etwas teurer als die Lösung mit dem bool, das
wäre noch zu testen.

lg

hustbaer

Wieso gerade std::set?

Kannst du nicht std::vector verwenden?
Statt Zeigern einfach Indexe speichern, und alle Objekte in den Vektor stopfen. Könnte leicht sein dass dadurch sogar alles schneller wird und auch weniger RAM braucht.

Vielleicht beschreibst du mal genauer was das für ne Datenstruktur ist (also vom logischen her, nicht wie du es jetzt genau umgesetzt hast). Sonst können wir auch nur raten.

nurf

Jockelx schrieb:

Wegen dem Alignment zeigt ein Pointer auf was gerades.
Zeigt er auf etwas ungerades, dann kann man daraus schliessen, dass da ein Bit per Hand gesetzt wurde.

So hab ich das verstanden. Also machbar aber schwachsinn.

Das funktioniert und höre ich nicht zum ersten mal.

Setzt natürlich viele Annahmen voraus, die man checken sollte, wenn ein neues Objekt erzeugt wird.

Prinzipiell gilt: Macht es genauso, obfuscated den Code noch und ihr habt euern Job sicher.