Infinite maze generating algorithm

I searched and even visited a maze-algorithm-collecting website, but nothing satisfies the following statements I require.
To make it clear, I need an infinite maze generating algorithm that follows:

makes a perfect maze, which is to say,
1. 2-dimensional and grid-based
2. each grid is either space or wall
3. every 2 spaces are linked and there's only one path
4. no 2x2 square is all space/wall (to make it look nice)
can provide a function that looks like f(s, x, y), where s is used for random seed or something like this
1. returns the type of grid at (x, y)
2. for different s within 0~(32768 or something), gives different results
infinite (probably limited by 64-bit int though)
extra space (I mean in program) is allowed

Clarification:

meaning of infinite here: something like this

function f(s, x, y){
    // for each x,y it gives a result, so we consider it "infinite"
    return (s*x+y)%32768<30 ? "wall" : "space";
}

this is a finite algorithm (satisfies 1)

init: filled with walls
choose a grid, tag it and add it to list
while (list is not empty)
{
    choose <x> randomly from the list
    delete <x> from the list
    if (<x> is tagged)
    {
        delete <x>
        continue
    }
    tag <x>
    if(number of surrounding walls ≤ 1)
    {
        add 4 surrounding walls to list
    }
}

something satisfying 1 and 3
we start from the Eller's Algorithm

it is generated row by row, and saves a set of regions

first row: all regions into a set, wall between regions (randomly)
while (not last row) {
    foreach (neighbour regions) {
        if (not in the same set) {
            break their wall and merge the regions (randomly)
        }
    }
    foreach (region) {
        break the wall below(randomly,and at least one does this)
    }
    generate next row
    for this row: {
        foreach (region) {
            if (connected with above) {
                merge to prev-set
            }
        }
        throw away prev-prev-set
    }
}
last row: connect all regions that are not in the same set

If we start from the centre and generate it circle by circle, it can be infinite; sadly we have rule 2.

Solution

I guess I need to explain my answer in detail.

Here is the code in javascript:

// C-flavour random
let gsrand = 0
function srand(x) { gsrand = x }
function rand() {
    gsrand = (gsrand*1103515245+12345)&0xffffffff
    return gsrand>>16 & 32767
}

class Chunk{
    matrix
    constructor() {
        // suppose the map is divided into 64×64 chunks
        this.matrix = new Uint8Array(4096)
    }
}

Chunk.prototype.put = function(x, y, type) {
    this.matrix[x<<6|y] = type == 'space' ? 0 : 1
}

/* * * Core * * */
Chunk.prototype.generate__infmaze_4 = function(lx, ly, rx, ry) { // split the map recursively
    let x0 = rx - lx
    let y0 = ry - ly
    // room small enough (width = 1)
    if(x0==0 || y0==0) {
        for(let i = lx; i <= rx; i++) {
            for(let j = ly; j <= ry; j++) this.put(i, j, 'space')
        }
        return
    }
    let mx = lx+2*(rand()%(x0>>1))+1
    let my = ly+2*(rand()%(y0>>1))+1
    for(let i = lx; i <= rx; i++) this.put(i, my, 'wall')
    for(let i = ly; i <= ry; i++) this.put(mx, i, 'wall')
    // split the map into four smaller rooms
    this.generate__infmaze_4(lx, ly, mx-1, my-1)
    this.generate__infmaze_4(lx, my+1, mx-1, ry)
    this.generate__infmaze_4(mx+1, ly, rx, my-1)
    this.generate__infmaze_4(mx+1, my+1, rx, ry)
    // three exits serve as passages through rooms
    let d = rand()%4
    let myl = (my-ly+1) >> 1
    let myr = (ry-my+1) >> 1
    let mxl = (mx-lx+1) >> 1
    let mxr = (rx-mx+1) >> 1
    if(d == 0) {
        this.put(rx - 2*(rand()%mxr), my, 'space')
        this.put(mx, ly + 2*(rand()%myl), 'space')
        this.put(mx, ry - 2*(rand()%myr), 'space')
    }
    else if(d == 1) {
        this.put(lx + 2*(rand()%mxl), my, 'space')
        this.put(mx, ly + 2*(rand()%myl), 'space')
        this.put(mx, ry - 2*(rand()%myr), 'space')
    }
    else if(d == 2) {
        this.put(lx + 2*(rand()%mxl), my, 'space')
        this.put(rx - 2*(rand()%mxr), my, 'space')
        this.put(mx, ry - 2*(rand()%myr), 'space')
    }
    else {
        this.put(lx + 2*(rand()%mxl), my, 'space')
        this.put(rx - 2*(rand()%mxr), my, 'space')
        this.put(mx, ly + 2*(rand()%myl), 'space')
    }
}
Chunk.prototype.generate__infmaze = function(x, y) {
    // chunks are isolated at first
    for(let i = 0; i < 64; i++) {
        this.put(i, 0, 'wall')
        this.put(0, i, 'wall')
    }
    // use the seed
    srand((x<<15 + y) ^ seed<<3)
    this.generate__infmaze_4(1, 1, 63, 63)
    // break the isolation between chunks
    let r1 = rand()%32
    this.put(2*(rand()%32) + 1, 0, 'space')
    this.put(0, 2*(rand()%32) + 1, 'space')
}

If you want to fit in the rules, simply let the s (in f(s, x, y)) be the seed used in srand and cache the data generated by new Chunk().generate__infmaze.

If you have noticed that this doesn't fit rule 1.3, you will also find it easy to fix it (change the break-the-isolation-between-chunks part, only that it may not look nice :).

Demo (seed = 0, (0, 0) ⇒ (63, 63)):

#############################.##################################
#.................................#.............................
#######.#########################################.##############
#...........#...#.#.#.........#.#.#.......................#.#.#.
###.#####.#.#.#.#.#.###.#####.#.#.#.#####################.#.#.#.
#.......#.#.#.#...#.#.#.#.#...#.#.#.#...#.......#.#.......#.#.#.
#####.###.###.#.#.#.#.#.#.###.#.#.#.#.###.###.###.#####.###.#.#.
#.#.#.#.#.#...#.#.#.....#.#.#.#.#.#.#.....#...............#.#...
#.#.#.#.#.#.###.#.#.###.#.#.#.#.#.#.#.#.#.###.#####.#######.#.#.
#.#.#.#.#.#.#.#.#...#...#...#...#.#.#.#.#.#.......#.........#.#.
#.#.#.#.#.#.#.#.#.#.#.###.#.#.#.#.#.###########.###########.#.#.
#.#.#.#.#...#...#.#.#...#.#...#.#.#.#...................#.#.#.#.
#.#.#.#.#.#.###.#.#.#########.#.#.#.#.#.#.#####.#######.#.#.#.#.
#.#...#.#.#.#...#.#.....#.....#.#.#.#.#.#.#...........#.#.#.#.#.
#.#.#.#.#.#.#####.#########.###.#.#.#.#.#.###.###########.#.#.#.
#...#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#...#...#.....#.#.#.#.
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#####.#.###.#.###.#.#.#.#.
#.#.#.#.#.#.#.#...#.#.#...#.#.#.#.#.#.#...#.#.........#.#.#.#.#.
#.#.#.#.#.#.#.#.#.#.#.#.###.#.#.#.#.#.#.#.#.###########.#.#.#.#.
#.#.#...#.#.#.#.#.#.#.#...#...#.#.#.#.#.#.#.#.............#.#.#.
#####.###.#.#.#.###.#.###.#.###.#.#.#.#.#.#####.#########.#.#.#.
#...#.#.#.#.#...#.#...#.......#.#...#...#.#.............#.#.#.#.
#.###.#.#.#.#.#.#.#.#.#.#####.#.#.#########################.#.#.
#.......#.#.#.#...#.#.#...#...#.#.#.......................#.#.#.
#.#.#.###.#.#.#.#####.#######.#.#.#######################.#.#.#.
#.#.#...#.#.#.#...#...........#.#.#...........................#.
#########.###################.#.#.###########################.##
#.......#.#.#.......#.........#.#.#.#...............#.....#.#.#.
#.#####.#.#.#.#.#######.#######.#.#.#.###############.#####.#.#.
#.#...#.#...#.#.#...#.#.#.....#.#.#.#.........#.....#.....#.....
#.#.#.#.#.#.#.#.###.#.#.#.#####.#.#.###.#########.#######.#.#.#.
#...#.#.#.#.#.#.#.#.#.........#.#.#.#.........#.....#.......#.#.
###.###.#.#.#.#.#.#.#.#.#######.#.#.###.#######.#####.#####.#.#.
#.....#.#.#.#.#.#.#.#.#.......#.#.#.................#.....#.#.#.
###.#.#.#.#.#.#.#.#.#.#.#.###.#.#.#############.#######.#####.#.
..#.#.#.#.#.#.#.#...#.#.#.#...#.#.#...#.#.#...#...#.#.....#.#.#.
#.#.#.#.#.#.#.#.###.#.#.#.#.###.#.#.#.#.#.###.#.#.#.#####.#.#.#.
#...#.#.#.#.#.#.....#.#.#.#...#.#.#.#.#.#...#...#.#.#...#.#.#.#.
#.#.#.#.#.#.#######.#########.#.#.#.#.#.#.#.#.#.#.#.#.###.#.#.#.
#.#.#.#.#.#.#.#...#.#...#.#...#.#.#.#...#.#...#.#.#.#.#.#.#.#.#.
#.###.#.#.#.#.#.#.#.###.#.#.#.#.#.#.#.###.#.#.#.#.#.#.#.#.#.#.#.
#...#.#.#.#.#.#.#.#.#...#.#.#.#.#.#.#.....#.#.#.#.#.#...#...#.#.
#######.###.#.#.#.#.#.###.#.#.#.#.#.#.#.#.#####.#.#.#.#.#.#.#.#.
#...#.#.#.#.#...#...#.....#.#.#.#.#.#.#.#.....#.#.#.#.#.#.#.#.#.
#.#.#.#.#.#.#.#.###.#.#.#.#.#.#.#.###.###.###.#.#.#.#.#.#.#.#.#.
#.#.#...#.#.#.#.#.#.#.#.#.#.#.#.#.#.#...#.#...#.#.#.#.#.#.#.#.#.
#.#.#.#.#.#.#.#.#.#.###.#####.#.#.#.#.#.###.#####.#.#.#.#.#.#.#.
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.....#.#.#.#.#...#.#.#.
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.###.###.#.#.#.#######.#.
#.#.#.#.#.#.#.#.#...#.#.#.#...#.#.#.#.#.#.#.#.#.#...#.#.#.#.#.#.
#.###.#.#.#.#####.###.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
#...#.#.#.#.#...#.....#.#.#.#.#.#.#.#.#.#.......#.#.#.#.#.#.#.#.
###.#.#.#.#.#.#.###.#.#.#.#.#.#.#.#.#.#.###########.#.#.#.#.#.#.
#.#.#.#.#.#.#.#.#.#.#.......#.#.#.#...#.#...............#.#.#.#.
#.#.#.#.#.#.#.###.#.###.#.#.#.#.#.###############.###.#.#.#.#.#.
#.....#.....#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.....#...#.#.#...#.#.#.
#######.#.###.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#######.#.#####.#.#.#.
#.....#.#.#.#.#.#.#.#...#.#.#.#...#.#.#...........#.#...#...#.#.
###.###.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#########.#.#.#.#.#.#.
#.......#...#.......#.#.#.#.#.#.#.#.#...#...#.......#.#...#.#.#.
#.#################################.#.###.#.#####.#.#.#.#.#.#.#.
#...............................#.#.#...#.#.#.....#.#.#.#.#.#.#.
###########################.###.#.#.#.#####.#.#####.#.#.#.#.#.#.
#.............................#...#.....#.........#.#.#.#.#.#.#.