Sign in to follow this  

[C#] Convert "1,2,3,4,5....,N" to "632,124,364,983, ...., etc".

This topic is 3576 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I have a need to turn a sequence into apparent randomness, and then be able to turn it back again. For instance, I pass it "1" it returns "636", I pass it "2" it returns "125". And it's completely reversible. I say reverse("636") and I get "1". The range of values for input is in the billions, so simply storing a lookup table isn't going to help. Know of any .NET libraries that are designed for this? So I don't have to go invent my own contraption. =/

Share this post


Link to post
Share on other sites
It all depends on how apparent you want the randomness to be. XOR is easy, fast, and trivially reversible.

Share this post


Link to post
Share on other sites
Quote:
Original post by Sneftel
It all depends on how apparent you want the randomness to be. XOR is easy, fast, and trivially reversible.


A simple XOR will not give the level of randomness I need. If I'm thinking straight, XOR would give me about B sequential series of consecutive numbers (I don't know if that makes logical sense) where B is the number of bits in the XOR code,

"1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,...."

Transforms into:

"100, 500, 400, 101, 501, 401, 102, 502, 402, 103,503,403"

Least, I think this is how it would look...

Edit:/ I cannot believe I'm googling for "reversible randomize function", lol..

Share this post


Link to post
Share on other sites
You might have better luck searching for "involution"/"involutary function", mathematical terms for a function is its own inverse or "reciprocal cipher" which is the cryptographic term for a encryption method that is its own inverse.

Share this post


Link to post
Share on other sites
I would just have a set pattern you use to switch up bits, then do an XOR to invert some of them.

value 0 0 0 1 0 1 0 1
bit 0 1 2 3 4 5 6 7

goes to

value 1 0 0 0 1 0 0 1
bit 3 6 2 0 7 1 4 5

then XOR with some mask
10001001 ^ 00101101 -> 10100100

to undo it just do it backward.

XOR with the same mask.
encoded mask
10100100 ^ 00101101 -> 10001001

Then reverse the scramble.

That should yield pretty random looking results.

EDIT:
or for even more random like results you could also set the seed of a random number. Use that random seed to generate a random number to do the mask with or even to switch bits with. Then when you save the number save the seed you used in front of the number.

Share this post


Link to post
Share on other sites
I'm still googling around, I'll try 'involution' in my search terms.

Bitwise operations in C# arn't fun.. I made a bug in my code just now, but I don't know if I really want to pursue using my own invention for this:

using System;
using System.Collections.Generic;
using System.Text;


class cBitShuffle
{
private const int MyCode = (unchecked((int)0xB00B1EE5));

private static void sSwapBit(ref int TheNumber, int TheLocation1, int TheLocation2)
{
if (!(TheLocation1 >= 0 && TheLocation1 < 32) ||
!(TheLocation2 >= 0 && TheLocation2 < 32))
throw new Exception("Location index must be in range [0..31].");

if (TheLocation1 == TheLocation2) return;

/* Get the bits. */
int TheBit1 = (TheNumber & (1 << TheLocation1)) > 0 ? 1 : 0;
int TheBit2 = (TheNumber & (1 << TheLocation2)) > 0 ? 1 : 0;

/* Clear bits. */
TheNumber &= (int)(0xFFFFFFFF ^ (1 << TheLocation1));
TheNumber &= (int)(0xFFFFFFFF ^ (1 << TheLocation2));

/* Set the bits. */
TheNumber |= TheBit1 << TheLocation2;
TheNumber |= TheBit2 << TheLocation1;
}

static int sEncode(int TheNumber)
{
/* First, NOR it with boobiees. */
TheNumber ^= MyCode;

/* Then swap like a flipflop. */
for (int TheLoop = 0; TheLoop < 32; TheLoop++)
sSwapBit(ref TheNumber, TheLoop, (TheLoop * 3) % 32);

return TheNumber;
}
static int sDecode(int TheNumber)
{
/* First, undo the swaps. */
for (int TheLoop = 0; TheLoop < 32; TheLoop++)
sSwapBit(ref TheNumber, TheLoop, (TheLoop * 3) % 32);

/* Then, undo the NOR it with boobiees. */
TheNumber ^= MyCode;

return TheNumber;
}

static void Main(string[] args)
{
for (int TheLoop = 0; TheLoop < 100; TheLoop++)
Console.WriteLine(TheLoop.ToString() + "\t" + sEncode(TheLoop) + "\t" + sDecode(sEncode(TheLoop)));
Console.ReadKey();
}
}

Share this post


Link to post
Share on other sites
Quote:
Original post by Thevenin
I'm still googling around, I'll try 'involution' in my search terms.

Bitwise operations in C# arn't fun.. I made a bug in my code just now, but I don't know if I really want to pursue using my own invention for this:

*** Source Snippet Removed ***


I think you want to loop backwards through the decode loop


static int sDecode(int TheNumber)
{
/* First, undo the swaps.*/
for (int TheLoop = 31; TheLoop >= 0; TheLoop--)
sSwapBit(ref TheNumber, TheLoop, (TheLoop * 3) % 32);

/* Then, undo the NOR it with boobiees. */
TheNumber ^= MyCode;

return TheNumber;
}

Share this post


Link to post
Share on other sites
Quote:
Original post by HappyCoder
I think you want to loop backwards through the decode loop


I think you're right! [smile]

I also noticed another mistake, and an optimization (check if TheBit1 == TheBit2) I should have put in.


Mistake (because result can be negative).
int TheBit1 = (TheNumber & (1 << TheLocation1)) > 0 ? 1 : 0;
int TheBit2 = (TheNumber & (1 << TheLocation2)) > 0 ? 1 : 0;
Correct
int TheBit1 = (TheNumber & (1 << TheLocation1)) == 0 ? 0 : 1;
int TheBit2 = (TheNumber & (1 << TheLocation2)) == 0 ? 0 : 1;

Output (not impressive):

0 1021392911 0
1 1021392910 1
2 1021523983 2
3 1021523982 3
4 1021392907 4
5 1021392906 5
6 1021523979 6
7 1021523978 7
8 1054947343 8
9 1054947342 9
10 1055078415 10
11 1055078414 11
12 1054947339 12
13 1054947338 13
14 1055078411 14
15 1055078410 15
16 1021392927 16
17 1021392926 17
18 1021523999 18
19 1021523998 19
20 1021392923 20
21 1021392922 21
22 1021523995 22
23 1021523994 23
24 1054947359 24
25 1054947358 25
26 1055078431 26
27 1055078430 27
28 1054947355 28
29 1054947354 29
30 1055078427 30
31 1055078426 31
32 1021384719 32
33 1021384718 33
34 1021515791 34
35 1021515790 35
36 1021384715 36
37 1021384714 37
38 1021515787 38
39 1021515786 39
40 1054939151 40
41 1054939150 41
42 1055070223 42
43 1055070222 43
44 1054939147 44
45 1054939146 45
46 1055070219 46
47 1055070218 47
48 1021384735 48
49 1021384734 49
50 1021515807 50
51 1021515806 51
52 1021384731 52
53 1021384730 53
54 1021515803 54
55 1021515802 55
56 1054939167 56
57 1054939166 57
58 1055070239 58
59 1055070238 59
60 1054939163 60
61 1054939162 61
62 1055070235 62
63 1055070234 63
64 1017198607 64
65 1017198606 65
66 1017329679 66
67 1017329678 67
68 1017198603 68
69 1017198602 69
70 1017329675 70
71 1017329674 71
72 1050753039 72
73 1050753038 73
74 1050884111 74
75 1050884110 75
76 1050753035 76
77 1050753034 77
78 1050884107 78
79 1050884106 79
80 1017198623 80
81 1017198622 81
82 1017329695 82
83 1017329694 83
84 1017198619 84
85 1017198618 85
86 1017329691 86
87 1017329690 87
88 1050753055 88
89 1050753054 89
90 1050884127 90
91 1050884126 91
92 1050753051 92
93 1050753050 93
94 1050884123 94
95 1050884122 95
96 1017190415 96
97 1017190414 97
98 1017321487 98
99 1017321486 99



Share this post


Link to post
Share on other sites
Quote:
Original post by HappyCoder
I would just have a set pattern you use to switch up bits, then do an XOR to invert some of them.


Tried that. I removed the loop and just swapped some of the bits I thought would have the most probably chance of returning drastically different numbers. The output I get is:

0       B00B96E5        0
1 300B96E5 1
2 B00B96E7 2
3 300B96E7 3
4 A00B96E5 4
5 200B96E5 5
6 A00B96E7 6
7 200B96E7 7
8 B00B96ED 8
9 300B96ED 9
10 B00B96EF 10
11 300B96EF 11
12 A00B96ED 12
13 200B96ED 13
14 A00B96EF 14
15 200B96EF 15
16 B00B96F5 16
17 300B96F5 17
18 B00B96F7 18
19 300B96F7 19
20 A00B96F5 20
21 200B96F5 21
22 A00B96F7 22
23 200B96F7 23
24 B00B96FD 24
25 300B96FD 25
26 B00B96FF 26
27 300B96FF 27
28 A00B96FD 28
29 200B96FD 29
30 A00B96FF 30
31 200B96FF 31
32 B00B96C5 32
33 300B96C5 33
34 B00B96C7 34
35 300B96C7 35
36 A00B96C5 36
37 200B96C5 37
38 A00B96C7 38
39 200B96C7 39
40 B00B96CD 40
41 300B96CD 41
42 B00B96CF 42
43 300B96CF 43
44 A00B96CD 44
45 200B96CD 45
46 A00B96CF 46
47 200B96CF 47
48 B00B96D5 48
49 300B96D5 49
50 B00B96D7 50
51 300B96D7 51
52 A00B96D5 52
53 200B96D5 53
54 A00B96D7 54
55 200B96D7 55
56 B00B96DD 56
57 300B96DD 57
58 B00B96DF 58
59 300B96DF 59
60 A00B96DD 60
61 200B96DD 61
62 A00B96DF 62
63 200B96DF 63
64 B00B96A5 64
65 300B96A5 65
66 B00B96A7 66
67 300B96A7 67
68 A00B96A5 68
69 200B96A5 69
70 A00B96A7 70
71 200B96A7 71
72 B00B96AD 72
73 300B96AD 73
74 B00B96AF 74
75 300B96AF 75
76 A00B96AD 76
77 200B96AD 77
78 A00B96AF 78
79 200B96AF 79
80 B00B96B5 80
81 300B96B5 81
82 B00B96B7 82
83 300B96B7 83
84 A00B96B5 84
85 200B96B5 85
86 A00B96B7 86
87 200B96B7 87
88 B00B96BD 88
89 300B96BD 89
90 B00B96BF 90
91 300B96BF 91
92 A00B96BD 92
93 200B96BD 93
94 A00B96BF 94
95 200B96BF 95
96 B00B9685 96
97 300B9685 97
98 B00B9687 98
99 300B9687 99

Share this post


Link to post
Share on other sites
Seriously, just use a block cipher. Take your numbers and encrypt them. Presto, seemingly random numbers. To get them back just decrypt. It's really that simple.

.NET already has everything you need.

Share this post


Link to post
Share on other sites
Quote:
Original post by Deaken Frost
...just use a block cipher. [...]


Block cipher looks like it could do it. However, a few things I hadn't throughly thought of arose and made me realize I should really tackle this at the source (in the database, in the stored procedure that originated this mess), I'm actually surprised that no one asked me "Why do you need to convert this sequence?" since that's usually the first question. My T-SQL is a bit hackish but, a solution nevertheless.


-- Find us a random character id that isn't already taken.
WHILE @TheShouldLoop = 1
BEGIN
SET @TheGenCharID = rand() * 2147483647;
SET @TheError = @@ERROR;
IF @TheError != 0 GOTO lblHandleError;

SET @TheCharacterCount = (SELECT COUNT(*) FROM fw_character WHERE
char_characterid = @TheGenCharID);
SET @TheError = @@ERROR;
IF @TheError != 0 GOTO lblHandleError;

IF(@TheCharacterCount = 0)
SET @TheShouldLoop = 0;
END



Speaking of SQL, I wonder if Superpig would mind converting my 100+ line SQL statements (that employ cursors, loops, etc) into 5 line "wonders" again.

Share this post


Link to post
Share on other sites
What version of SQL Server are you using? Doing that at the T-SQL level is not efficient (or even close to it)... if you are using 2005 you can use the crypto functions built in, or write a CLR procedure. Even in 2000 you could write a user defined function, compile it to a DLL, and call that.

I don't know why you are doing this but it isn't something that should be done in the database, at least not like that.

Share this post


Link to post
Share on other sites
A simple sequence which should yield reasonable results is (x + x0)^2 + c mod p where x0 and c are arbitrary parameters and p is a prime over twice the size of the largest number you need to "randomize" (this becomes important later).

Now to decode this we have

   e = (x + x0)^2 + c mod p
=> (x + x0)^2 = e - c mod p


And so we can find x + x0 by applying the Shanks-Tonelli algorithm which will yield two roots, from these we can calculate two values for x and we can select the correct value based on the fact that all of our x are in the range [0, p / 2].

Share this post


Link to post
Share on other sites
Quote:
Original post by krez
Doing that at the T-SQL level is not efficient (or even close to it)...


The code is a bit juvenile, but it'd never be a bottleneck. This code is only executed when a new account is created, and given that collisions are very rare (even when the database gets large; the server would roll-over and die long before collisions became too common for this method to work) and that the query that checks for collisions is just a simple select on a primary key, it's going to complete very very very fast.

Quote:
Original post by krez
I don't know why you are doing this but ...


In most MMORPGs your (ASCII) name is a unique identifier (at least for each realm). In Frostwinds your (UTF-8) name is not unique. Thus it's possible for you and all your friends to be named "龙火".

In addition to a well featured "buddy list" component, 8 digit hex numbers are displayed in small print on the forums, and via a right click option in-game.

Pictar (from Frostwinds forum)


It would be very lame if this hex code started at 00000000 and worked its way up. So it needs to be random. At the moment the code to generate it is quite horrific, and this T-SQL code I wrote should be quite an improvement.

Share this post


Link to post
Share on other sites

class randomIdCollection {
std::vector <int> forward;
std::map<int, int> reverse;

public:
int translate_forward(int index) {
if (index > forward.size()) { throw std::out_of_bounds(); } // or something
return forward[index];
}
int translate_backward(int value) {
std::map<int, int>::iterator it = reverse.find(value);
if (it == reverse.end()) { throw std::out_of_bounds(); } // or something
return it->second;
}
void generate() {
int value;
do { value = getRandomValue(); }
while (std::find(forward.begin(), forward.end(), value) != forward.end());
reverse[value] = forward.size();
forward.push_back(value);
}
};

Share this post


Link to post
Share on other sites
Why not use MSSQL's* GUID generator NEWID(), store it in the user's record (using the function as the default value is even easier) and be done with it? Why does it have to be reversible?

* I believe that's the engine you're using, right?

Share this post


Link to post
Share on other sites
Quote:
It would be very lame if this hex code started at 00000000 and worked its way up.


its very lame to take what should be a trivial implementation detail, and make it complicated to the point of needing help to get it right.

KISS

Share this post


Link to post
Share on other sites
Quote:
Original post by thedustbustr
Quote:
It would be very lame if this hex code started at 00000000 and worked its way up.


its very lame to take what should be a trivial implementation detail, and make it complicated to the point of needing help to get it right.


You mean that it's lame to ask a very concise cryptological question and then diverge the discussion into what I'm trying to accomplish (on a higher level) and how best to do it.

Although I agree with you, and I'd like GameDev to take a more ExpertsExchange approach ("[solved]" "[unsolved]" tags). The adminstrators here don't. I'm pretty sure topic divergence is still a common occurance around here; though I haven't been active here in a couple years.

And at the very least, bare with me here, the divergence occurred because the most straight-forward advice I was being given was also wrong advice; XOR and bit-shifting doesn't work (I think I even (correctly)predicted the pattern that would result in the second post).

Quote:
Original post by thedustbustr
Why not use MSSQL's* GUID generator NEWID(), store it in the user's record (using the function as the default value is even easier) and be done with it? Why does it have to be reversible?


Can I specify the length of a GUID? Although the user isn't going to be typing these 8 digit hex keys on a regular basis (if ever), they need to be able to differentiate between which key is their friend, and which key is the name-fake user. I expect my players to be able to memorize the keys of people they trust in the game, or at the least, be able (to a high-degree of accuracy) to spot a wrong key.

With GUID, that's quite a bit of digits, about this many ->"3F25-04E0-4F89-11D3-9A0C-0305-E82C-3301" if I'm reading this right.

And a bigger problem, GUIDs are not unique (despite its name). MSSQL may do some automated stuff to assist me in having GUIDs as primary keys (presuming I can do that) but I'd still be using a loop in the stored procedure. The difference is that the frequency of collisions would be sooo small that I'd almost be comfortable telling someone "trust me, it'll never happen".

And the only time it has to be reversible is when it's mapping "1,2,3" to "632","142","535". Perhaps I'd best explain it with the following diagrams:


System 1 (original topic):

To get random and unique 8 digit hex keys (ex "3F426285" "6F4662A") for the user, build a PRIMARY KEY as an INT and set it to AUTO_INCREMENT (by 1) starting at 0. Then, before the value of the PRIMARY KEY is displayed to the user (because it'll be "0,1,2,3,4"), map it to my reversible-randomize function ("646","252","845"). In which, a reverse function is needed to convert user input (aka "Delete character [252]") to the subsequent SQL query ("DELETE FROM tb_characters WHERE char_id=1;");.

System 2 (diverged topic):

To get random and unique 8 digit hex keys (ex "3F426285" "6F4662A") for the user, build a PRIMARY KEY as an INT, and probe it with random numbers( via rand()) until one is found that isn't already taken. This key can be displayed to the user without the need of passing it through a mapping function, and it subsequently doesn't have to be reversed.


Quote:
Original post by Zahlman
std::vector <int> forward;
std::map<int, int> reverse;

do { value = getRandomValue(); }
while (std::find(forward.begin(), forward.end(), value) != forward.end());
reverse[value] = forward.size();
forward.push_back(value);


You've given it STATE! [bawling]
(But your code would work)

If I'm reading this right (because C++ is an eye-sore), you're making a resizable lookup table. Whenever a new account is registered, you assign the value of the account number X (example "1") to this class which maps it to a random (and unique) value Y (example "6326363"). I don't like your use of std::find, since it appears that this is going to be both linear and a memory-hog when the list grows large, nor do I much like that this converter now has state that I need to carefully preserve (which I'd best do by rewriting this code in the T-SQL language using a table that maps PK x and UK y (y of which, would be computed by probing the table with rand() to find an empty slot, much like how my current T-SQL solution does), and since calls to this generate() would be ASYNC (two people try to create an account at the same time) and thus, need to be SYNC'd via BEGIN TRANSACTION)) but it would work.



I think this thread is solved, lol...

Share this post


Link to post
Share on other sites
Quote:
Original post by Thevenin
Quote:
Original post by WanMaster
Why not use MSSQL's* GUID generator NEWID(), store it in the user's record (using the function as the default value is even easier) and be done with it? Why does it have to be reversible?

Can I specify the length of a GUID?

No you can't. You can cast it to a string and truncate it, but that would seriously damage it uniqueness.

Quote:
Although the user isn't going to be typing these 8 digit hex keys on a regular basis (if ever), they need to be able to differentiate between which key is their friend, and which key is the name-fake user. I expect my players to be able to memorize the keys of people they trust in the game, or at the least, be able (to a high-degree of accuracy) to spot a wrong key.

Not to criticize your design, but is forcing people to memorize or recognize a random sequence of characters really the best solution?

Quote:
With GUID, that's quite a bit of digits, about this many ->"3F25-04E0-4F89-11D3-9A0C-0305-E82C-3301" if I'm reading this right.

Correct.

Quote:

And a bigger problem, GUIDs are not unique (despite its name). MSSQL may do some automated stuff to assist me in having GUIDs as primary keys (presuming I can do that) but I'd still be using a loop in the stored procedure.

Quote:
And the only time it has to be reversible is when it's mapping "1,2,3" to "632","142","535".

I still don't understand the need of them, nor why they have to be reversible. However, if the about uniqueness and the ability to map them to (auto incrementing) integers, why not generate a table for them, consisting only of a primary integer key and a field for the unique code, and generate a couple of million (or whatever you'll need in the next ten years) records with any random function you like? A table lookup will probably outperform any random or hash function you write: its key is unique, it will have a clustered index and the code is a fix length char array. A database select query doesn't get any faster than that.

I'd say keep it simple and make use of the incredible optimizations in the database engine itself. And if you are concerned with state: the entire database is nothing but state.

Quote:
I think this thread is solved, lol...

Couldn't resist to reply anyway. [smile]

Share this post


Link to post
Share on other sites
Quote:
Original post by WanMaster
Not to criticize your design, but is forcing people to memorize or recognize a random sequence of characters really the best solution?


Given that Unicode name support is a must, it was the only solution. Thus it's inherently the worst solution, and the best solution. Dunno if it's a good solution though.

This is a bit confusing.
But unicode character list is awesome!
I miss playing with my pixelated Friends from Europe/Brazil/China/Japan. =(


Quote:
Quote:
I think this thread is solved, lol...

Couldn't resist to reply anyway. [smile]

...

So how was your day? lol [grin]

A friend of mine (who's also a lab partner of mine) intends on dropping this semester's communication systems course (3rd year computer engineering). I'm so sad -- curse this University and its extortion on students. [bawling]

[Edited by - Thevenin on March 3, 2008 5:13:00 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by Thevenin
You've given it STATE! [bawling]
(But your code would work)


[lol]

Quote:
If I'm reading this right (because C++ is an eye-sore), you're making a resizable lookup table. Whenever a new account is registered, you assign the value of the account number X (example "1") to this class which maps it to a random (and unique) value Y (example "6326363"). I don't like your use of std::find, since it appears that this is going to be both linear and a memory-hog when the list grows large,


It ought to just look up in the map instead, which would be O(lg N). I don't know why I changed that from what I had originally. :S

Share this post


Link to post
Share on other sites

This topic is 3576 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this