I believe the following is equivalent. It gets rid of some of the tensor copying. On my machine I'm seeing a factor of almost 3 in speed improvement.

LinearComplexityC2 = Compile[{{u, _Integer, 1}},
   Module[{len, b, c, l = 0, m = 0, bsub, mmn, oldl, oldm},
    len = Length[u];
    c = b = Join[{1}, Table[0, {len - 1}]];
    Do[
     If[OddQ[u[[n]] + Sum[c[[j + 1]]*u[[n - j]], {j, 1, l}]],
      oldl = l;
      oldm = m;
      bsub = b[[1 ;; l + 1]];
      If[2*l <= n, l = n - l; m = n; b = c;];
      mmn = 1 + n - oldm;
      c[[mmn ;; mmn + oldl]] =
       Mod[c[[mmn ;; mmn + oldl]] + bsub, 2];
      ], {n, 1, len}];
    l], CompilationTarget -> "C"
   ];

I believe the following is equivalent. It gets rid of some of the tensor copying. On my machine I'm seeing a factor of almost 3 in speed improvement.

LinearComplexityC2 = Compile[{{u, _Integer, 1}},
   Module[{len, b, c, l = 0, m = 0, bsub, mmn, oldl, oldm},
    len = Length[u];
    c = b = Join[{1}, Table[0, {len - 1}]];
    Do[
     If[OddQ[u[[n]] + Sum[c[[j + 1]]*u[[n - j]], {j, 1, l}]],
      oldl = l;
      oldm = m;
      bsub = b[[1 ;; l + 1]];
      If[2*l <= n, l = n - l; m = n; b = c;];
      mmn = 1 + n - oldm;
      c[[mmn ;; mmn + oldl]] =
       Mod[c[[mmn ;; mmn + oldl]] + bsub, 2];
      ], {n, 1, len}];
    l], CompilationTarget -> "C"
   ];

--- edit ---

Adding

"RuntimeOptions" -> "Speed"

gives another factor of 3 or so.

--- end edit ---

I believe the following is equivalent. It gets rid of some of the tensor copying. On my machine I'm seeing a factor of almost 3 in speed improvement.

--- edit ---

No, not equivalent. Will try to find the bug...

--- end edit ---

LinearComplexityC2 = Compile[{{u, _Integer, 1}},
   Module[{len, b, c, l = 0, m = 0, bsub, mmn},
    len = Length[u];
    c = b = Join[{1}, Table[0, {len - 1}]];
    Do[
     If[OddQ[u[[n]] + Sum[c[[j + 1]]*u[[n - j]], {j, 1, l}]],
      If[2*l <= n, l = n - l; m = n; bsub = b[[1 ;; l + 1]]; b = c;
       , bsub = b[[1 ;; l + 1]]];
      mmn = 1 + n - m;
      c[[mmn ;; mmn + l]] =
       Mod[c[[mmn ;; mmn + l]] + bsub, 2];
      ], {n, 1, len}];
    l], CompilationTarget -> "C"
   ];

I believe the following is equivalent. It gets rid of some of the tensor copying. On my machine I'm seeing a factor of almost 3 in speed improvement.

LinearComplexityC2 = Compile[{{u, _Integer, 1}},
   Module[{len, b, c, l = 0, m = 0, bsub, mmn, oldl, oldm},
    len = Length[u];
    c = b = Join[{1}, Table[0, {len - 1}]];
    Do[
     If[OddQ[u[[n]] + Sum[c[[j + 1]]*u[[n - j]], {j, 1, l}]],
      oldl = l;
      oldm = m;
      bsub = b[[1 ;; l + 1]];
      If[2*l <= n, l = n - l; m = n; b = c;];
      mmn = 1 + n - oldm;
      c[[mmn ;; mmn + oldl]] =
       Mod[c[[mmn ;; mmn + oldl]] + bsub, 2];
      ], {n, 1, len}];
    l], CompilationTarget -> "C"
   ];